Anonymous user
Cipolla's algorithm: Difference between revisions
m
→{{header|Sage}}: Fixed a few stray bugs and updated algorithm for cases where p is not prime.
(→{{header|FreeBASIC}}: added GMP version) |
m (→{{header|Sage}}: Fixed a few stray bugs and updated algorithm for cases where p is not prime.) |
||
Line 827:
return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p)
def cipollaAlgorithm(a, p
out = []▼
return False▼
if eulerCriterion(a, p) == -1:
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)]▼
conglst = [] #congruence list
▲ out = []
crtlst = []
factors = []
for k in list(factor(p)):
for f in factors:
conglst.append(cipollaAlgorithm(a, f))
for i in Permutations([0, 1] * len(factors), len(factors)).list():
for j in range(len(factors)):
crtlst.append(int(conglst[ j ][ i[j] ]))
out.append(crt(crtlst, factors))
▲ if pow(p, 1, 4) == 3:
return [temp, p - temp]
t = randrange(2, p)
u = pow(t**2 - a, 1, p)
▲ while (eulerCriterion(u, p) == 1):
▲ t = randrange(2, p)
▲ u = pow(t**2 - a, 1, p)
out.extend([x,
▲ out.append(x)
return sorted(out)
| |||