Rosetta Code

Cipolla's algorithm: Difference between revisions

Page Discussion

Cipolla's algorithm (view source)

Revision as of 23:03, 10 April 2017

375 bytes added ,  7 years ago
→‎{{header|Sage}}
(added FreeBASIC)
Line 642:
 
=={{header|Sage}}==
{{works with|Sage|7.16}}
 
Sage provides functions to construct a finite number field, modulo p*p, with polynomial x^2-ω², and this is precisely what we need.
<lang sage>
def CipollaeulerCriterion(na, p) :
return -1 if notpow(a, is_primeint((p-1)/2), p) == p-1 else :1
 
print ("❌ %d is not a prime" % p)▼
def cipollaMult(x1, y1, x2, y2, u, p):
return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p)
 
def cipollaAlgorithm(a, p, t):
if not is_prime(p):
▲ print ("❌ %d" + str(p) + " is not a prime." % p)
return False
if legendre_symboleulerCriterion(na, p) !== -1 :
print ("❌ %d" + str(a) + " is not a squarequadratic residue modulo %d" %+ str(n,p))
return False
 
for a in range (2,n) :▼
a = if legendre_symbolpow(a*a-n,p) == -1, :p)
out = break[]
 
omega2 = a*a - n
Q.<x>for =i PolynomialRingin range(GF(p)t):
R.<x> = GF(p*p,modulus t = x^randrange(2-omega2, p)
r u = pow(at**2 +- x)a, ^1, ((p+1)/2)
while (eulerCriterion(u, p) == 1):
return r, p-r▼
t = randrange(2, p)
u = pow(t**2 - a, 1, p)
 
x0, y0 = t, 1
x, y = t, 1
▲ for ai in range (int((p + 1) / 2,n) - 1):
x, y = cipollaMult(x, y, x0, y0, u, p)
 
if x not in out:
out.append(x)
 
▲ return r, p-rsorted(out)
</lang>
{{out}}
<pre>
sage: CipollacipollaAlgorithm( 10, 13, 30)
([6, 7)]
sage: CipollacipollaAlgorithm(56, 101, 30)
([37, 64)]
sage: CipollacipollaAlgorithm(8218, 10007, 30)
[135, 9872]
(9872, 135)
sage: Cipolla cipollaAlgorithm(331575, 1000003, 30)
[144161, 855842]
(855842, 144161)
sage: Cipolla cipollaAlgorithm(8219, 10007, 30)
❌ 8219 is not a squarequadratic residue modulo 10007
False
</pre>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/266399"