6. 模(Mod)指數計算 X^P (mod N)

# 勉強用到，雖然有點投機

namespace Q6
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            // A = B % N
            // then: 
            //   a. A+Y=(B+Y)%N
            //   b. AX=BX%N
            //   c. (B%N)^P=B^P

            var X = int.Parse(textBox1.Text);
            var P = int.Parse(textBox2.Text);
            var N = int.Parse(textBox3.Text);

            label3.Text = "餘數 = " + calc(X % N, P, N);
        }

        int calc(int X, int P, int N)
        {
            if (P == 1) return X;
            if (P % 2 == 1)
                return calc(X, P - 1, N) * X % N;
            var k = calc(X, P / 2, N) % N;
            return k * k % N;
        }

        private void button3_Click(object sender, EventArgs e)
        {
            Close();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            textBox1.Clear();
            textBox2.Clear();
            textBox3.Clear();
            label3.Text = "餘數 = ";
        }
    }
}

}