Return to Answer

removed typos

Source Link

edited Sep 28, 2018 at 5:43

in your legendre_symbol implementation, you compute pow(a, (p - 1)/2, p). You don't need to subtract 1 from p, since p is odd. Also, you can replace p/2 with p >> 1, which is faster.
in your simple case handling, you can replace p % 4 with p & 3 and again, pow(a, (p + 1)/4, p) with pow(a, (p + 1) >> 2, p). Since you have checked that p & 3 == 3, an equivalent solution would be pow(a, (p >> 2) + 1, p), I would go for this one instead. It can make a difference when the right shift effectively reduces the byte size of p.
there is another simple case you can check for: p % 8 == 5 otor the equivalent p & 7 == 5. In that case, couyou can compute pow(a, (p >> 3) + 1, p), check if it is a solution (it is a solution if and only if a is quartic residue modulemodulo p), otherwise multiply that with pow(2, p >> 2, p) to get a valid solution (and don't forget to calculate % p after the multiplication of course)

in your while-loop, you need to find a fitting i. Let's see what your implementation is doing there if i is, for example, 34:

 pow(t, 2, p)
 pow(t, 4, p)   # calculates pow(t, 2, p)
 pow(t, 8, p)   # calculates pow(t, 4, p), which calculates pow(t, 2, p)
 pow(t, 16, p)  # calculates pow(t, 8, p), which calculates pow(t, 4, p), which calculates pow(t, 2, p)

    i, t2i, = 0, t
    for i in range(1, m):
        t2i = t2i**2t2i * t2i % p
        if t2i == 1:
            break

in your legendre_symbol implementation, you compute pow(a, (p - 1)/2, p). You don't need to subtract 1 from p, since p is odd. Also, you can replace p/2 with p >> 1, which is faster.
in your simple case handling, you can replace p % 4 with p & 3 and again, pow(a, (p + 1)/4, p) with pow(a, (p + 1) >> 2, p). Since you have checked that p & 3 == 3, an equivalent solution would be pow(a, (p >> 2) + 1, p), I would go for this one instead. It can make a difference when the right shift effectively reduces the byte size of p.
there is another simple case you can check for: p % 8 == 5 ot the equivalent p & 7 == 5. In that case, cou can compute pow(a, (p >> 3) + 1, p), check if it is a solution (it is a solution if and only if a is quartic residue module p), otherwise multiply that with pow(2, p >> 2, p) to get a valid solution (and don't forget to calculate % p after the multiplication of course)

in your while-loop, you need to find a fitting i. Let's see what your implementation is doing there if i is, for example, 3:

 pow(t, 2, p)
 pow(t, 4, p)   # calculates pow(t, 2, p)
 pow(t, 8, p)   # calculates pow(t, 4, p), which calculates pow(t, 2, p)
 pow(t, 16, p)  # calculates pow(t, 8, p), which calculates pow(t, 4, p), which calculates pow(t, 2, p)

    i, t2i, = 0, t
    for i in range(1, m):
        t2i = t2i**2 % p
        if t2i == 1:
            break

in your legendre_symbol implementation, you compute pow(a, (p - 1)/2, p). You don't need to subtract 1 from p, since p is odd. Also, you can replace p/2 with p >> 1, which is faster.
in your simple case handling, you can replace p % 4 with p & 3 and again, pow(a, (p + 1)/4, p) with pow(a, (p + 1) >> 2, p). Since you have checked that p & 3 == 3, an equivalent solution would be pow(a, (p >> 2) + 1, p), I would go for this one instead. It can make a difference when the right shift effectively reduces the byte size of p.
there is another simple case you can check for: p % 8 == 5 or the equivalent p & 7 == 5. In that case, you can compute pow(a, (p >> 3) + 1, p), check if it is a solution (it is a solution if and only if a is quartic residue modulo p), otherwise multiply that with pow(2, p >> 2, p) to get a valid solution (and don't forget to calculate % p after the multiplication of course)

in your while-loop, you need to find a fitting i. Let's see what your implementation is doing there if i is, for example, 4:

 pow(t, 2, p)
 pow(t, 4, p)   # calculates pow(t, 2, p)
 pow(t, 8, p)   # calculates pow(t, 4, p), which calculates pow(t, 2, p)
 pow(t, 16, p)  # calculates pow(t, 8, p), which calculates pow(t, 4, p), which calculates pow(t, 2, p)

    i, t2i, = 0, t
    for i in range(1, m):
        t2i = t2i * t2i % p
        if t2i == 1:
            break

Source Link

created Sep 27, 2018 at 6:35

Aemyl

I know, this is a bit late but I have some more minor optmimization suggestions:

in your legendre_symbol implementation, you compute pow(a, (p - 1)/2, p). You don't need to subtract 1 from p, since p is odd. Also, you can replace p/2 with p >> 1, which is faster.
in your simple case handling, you can replace p % 4 with p & 3 and again, pow(a, (p + 1)/4, p) with pow(a, (p + 1) >> 2, p). Since you have checked that p & 3 == 3, an equivalent solution would be pow(a, (p >> 2) + 1, p), I would go for this one instead. It can make a difference when the right shift effectively reduces the byte size of p.
there is another simple case you can check for: p % 8 == 5 ot the equivalent p & 7 == 5. In that case, cou can compute pow(a, (p >> 3) + 1, p), check if it is a solution (it is a solution if and only if a is quartic residue module p), otherwise multiply that with pow(2, p >> 2, p) to get a valid solution (and don't forget to calculate % p after the multiplication of course)

in your while-loop, you need to find a fitting i. Let's see what your implementation is doing there if i is, for example, 3:

 pow(t, 2, p)
 pow(t, 4, p)   # calculates pow(t, 2, p)
 pow(t, 8, p)   # calculates pow(t, 4, p), which calculates pow(t, 2, p)
 pow(t, 16, p)  # calculates pow(t, 8, p), which calculates pow(t, 4, p), which calculates pow(t, 2, p)

do you see the redundancy? with increasing i, the number of multiplications grows quadratically, while it could just grow linear:

    i, t2i, = 0, t
    for i in range(1, m):
        t2i = t2i**2 % p
        if t2i == 1:
            break

the last optimization is a rather simple one: I would just replace
```
 t = (t * b * b) % p
 c = (b * b) % p
```

with

    c = (b * b) % p
    t = (t * c) % p

which saves one multiplication