Closed beaurancourt closed 1 year ago
The original explanation implied that x^(1/4) mod N = x^(((p-1)*(q-1)+4)/8) mod N, but checking fact 2.160 from the Handbook of Applied Cryptography:
x^(1/4) mod N = x^(((p-1)*(q-1)+4)/8) mod N
the text says that this is a formula for square roots not fourth roots. Thus, to get the fourth root, we apply the formula twice.
All committers have signed the CLA.
Can confirm, this tripped us up!
Great catch! I've added the explicit formula to your edit and mentioned that the exponent only needs to be computed once as it does not depend on the input.
The original explanation implied that
x^(1/4) mod N = x^(((p-1)*(q-1)+4)/8) mod N
, but checking fact 2.160 from the Handbook of Applied Cryptography:the text says that this is a formula for square roots not fourth roots. Thus, to get the fourth root, we apply the formula twice.