Anonymous user
Cipolla's algorithm: Difference between revisions
m
→{{header|Sage}}: Replaced broken Sage code in previous edit, now updating for efficiency and errors
m (→{{header|Sage}}: Replaced broken Sage code in previous edit, now updating for efficiency and errors) |
|||
Line 650:
return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p)
def cipollaAlgorithm(a, p, t = 10):
if not is_prime(p):
print "❌ " + str(p) + " is not a prime."
Line 657:
print "❌ " + str(a) + " is not a quadratic residue modulo " + str(p)
return False
if pow(p, 1, 4) == 3:
return [pow(a, int((p-1)/4), p), -pow(a, int((p-1)/4), p)]
a = pow(a, 1, p)
Line 680 ⟶ 682:
{{out}}
<pre>
sage: cipollaAlgorithm(10, 13
[6, 7]
sage: cipollaAlgorithm(56, 101
[37, 64]
sage: cipollaAlgorithm(8218, 10007
[135, 9872]
sage: cipollaAlgorithm(331575, 1000003
[144161, 855842]
sage: cipollaAlgorithm(8219, 10007
❌ 8219 is not a quadratic residue modulo 10007
False
| |||