pow22523 method
Pow22523 set v = x^((p-5)/8), and returns v. (p-5)/8 is 2^252-3.
Implementation
void pow22523(Element x) {
Element t0 = Element.feZero();
Element t1 = Element.feZero();
Element t2 = Element.feZero();
t0.square(x); // x^2
t1.square(t0); // x^4
t1.square(t1); // x^8
t1.multiply(x, t1); // x^9
t0.multiply(t0, t1); // x^11
t0.square(t0); // x^22
t0.multiply(t1, t0); // x^31
t1.square(t0); // x^62
for (int i = 1; i < 5; i++) {
// x^992
t1.square(t1);
}
t0.multiply(t1, t0); // x^1023 -> 1023 = 2^10 - 1
t1.square(t0); // 2^11 - 2
for (int i = 1; i < 10; i++) {
// 2^20 - 2^10
t1.square(t1);
}
t1.multiply(t1, t0); // 2^20 - 1
t2.square(t1); // 2^21 - 2
for (int i = 1; i < 20; i++) {
// 2^40 - 2^20
t2.square(t2);
}
t1.multiply(t2, t1); // 2^40 - 1
t1.square(t1); // 2^41 - 2
for (int i = 1; i < 10; i++) {
// 2^50 - 2^10
t1.square(t1);
}
t0.multiply(t1, t0); // 2^50 - 1
t1.square(t0); // 2^51 - 2
for (int i = 1; i < 50; i++) {
// 2^100 - 2^50
t1.square(t1);
}
t1.multiply(t1, t0); // 2^100 - 1
t2.square(t1); // 2^101 - 2
for (int i = 1; i < 100; i++) {
// 2^200 - 2^100
t2.square(t2);
}
t1.multiply(t2, t1); // 2^200 - 1
t1.square(t1); // 2^201 - 2
for (int i = 1; i < 50; i++) {
// 2^250 - 2^50
t1.square(t1);
}
t0.multiply(t1, t0); // 2^250 - 1
t0.square(t0); // 2^251 - 2
t0.square(t0); // 2^252 - 4
multiply(t0, x); // 2^252 - 3 -> x^(2^252-3)
}