[Tutor] Actual code that illustrates problem
Kermit Rose
kermit at polaris.net
Thu Aug 17 05:42:08 CEST 2006
Message: 11
Date: Tue, 15 Aug 2006 11:50:47 +1200
From: "John Fouhy" <john at fouhy.net>
Subject: Re: [Tutor] Global variables
Cc: tutor at python.org
Can you post actual code to illustrate the problem? Don't post your
entire module; just show us the functions involved, the input that
causes the problem, and what output you expect to get.
--
John.
*******
Here is the output that illustratrates the problem. After the output I'll
list the code for the called function,
strongfac,
and the calling function, fermat.
IDLE 1.1.2
>>> import factor34
>>> from factor34 import testrange
>>> testrange(10**14+37,10**14+37)
Begin calculating constants to be used in factoring.
Finished calculating constants to be used in factoring.
Search for a factor of 100000000000037
Could not find factors by strong probable prime test using witnesses <
10000.
Try to find factors by using power of 2 mod z as a witness.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 0 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 1 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 2 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 3 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 4 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 5 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 6 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 7 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 8 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 9 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 10 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 11 x = 0 y = 0 face = [0, 0, 0]
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 12 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 15306543515214
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 13 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 12123044576953
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 14 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 45391315949900
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 15 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 59571344259390
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 16 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 78029752396948
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 17 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 35863146075772
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 18 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 19712913203085
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 19 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 14607414373499
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 20 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 57761947468766
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 21 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 75604347243674
.
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 22 x = 0 y = 0 face = [0, 0, 0]
In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes 3561873332543
Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
In strongfac
Found1: x = 1858741
Found1: y = 53799857
face = [1858741L, 53799857L, 0]
Found1: factor by strong probable prime test, using witnes 96058894729069
.
Found1: factors are 1858741 53799857
Found1: returning [1858741L, 53799857L, 0] to fermat routine.
Retrieved from strongfac, face = [1858741L, 53799857L, 0]
In fermat: k = 23 x = 1858741 y = 53799857 face = [1858741L,
53799857L, 0]
index of torial is 23
z = 100000000000037 x = 1858741 y = 53799857 difficulty = 0
>>>
# def strongfac(z,w):
# x = gcd(z,w-1)
# if x > 1:
# if x < z:
# y = z/x
# print "Found factors by P-1 Method as part of Strong
probable prime test, using witness",w,"."
# print " x = ",x," y = ",y
# return [x,y,0]
# w2 = (w * w)%z
# s = ksqrt(w2)
# if w2 == s * s:
# if s != w:
# x = gcd(z,kabs(w2 - s))
# if x > 1:
# if x < z:
# print "Found factors by square = square as part of
Strong probable prime test, using witness",w,"."
# return [x,y,0]
#
# trace = 0
# t = z - 1
# a = 0
# while t%2 == 0:
# t = t/2
# a = a + 1
# test = pow(w,t,z)
# if test ==1:
# x = gcd(z,w-1)
# if x > 1:
# if x < z:
# y = z/x
# print " Found factor by Strong probable prime test,
using withness ",w,"."
# return [x,y,0]
# else:
# x = gcd(test-1,z)
# if x > 1:
# print " "
# print " In strongfac "
# print " Found1: x = ",x
# if x < z:
# y = z/x
# print " Found1: y = ",y
# face = [x,y,0]
# print " face = ",face
# face[0] = x
# face[1] = y
# face[2] = 0
# print " Found1: factor by strong probable prime test,
using witness ",w," ."
# print " Found1: factors are ",face[0],face[1]
# print " Found1: returning ",face," to fermat routine."
# return face
#
# if test + 1 == z:
# x = gcd(w+1,z)
# if x > 1:
# if x < z:
# y = z/x
# print " Found factor by Strong probable prrime test,
using withness ",w,"."
# return [x,y,0]
# for j in range (1,a):
# test2 = (test * test)%z
# test2sqrt = ksqrt(test2)
# if test2sqrt * test2sqrt == test2:
# diff = kabs(test - test2sqrt)
# if diff !=0:
# x = gcd(z,kabs(test - test2sqrt))
# if x > 1:
# if x < z:
# y = z/x
# print " Found factors by strong probable prime
test using difference of squares and witness ",w,"."
# return [x,y,j]
# y = gcd(z,test+test2sqrt)
# if y > 1:
# if y < z:
# print " Found factors by strong probable prime test
using difference of squares and witness ",w,"."
# return [x,y,j]
# test1 = test2 + 1
# test = test2
# if test1 == z:
# pass
# else:
# x = gcd(test1,z)
# if x > 1:
# if x < z:
# print " "
# print " In Strongfac "
# y = z/x
# fac = [x,y,j]
# print " Foundj factor by strong probable prime test
using witness,",w," ."
# print " Returning ",fac," to fermat routine."
# return fac
# q = 0
# fac = [0,0,0]
# return fac
#
# def fermat(z,maxdiff,pmap,plist,sqlist,sqresidue,torials,limitsteps):
# for j in range(2,3):
# print " "
# print " Try to find factors by using power of ",j," mod z as a
witness."
# w2 = j
# for k in range(100):
# w = pow(j,torials[k],z)
# face = strongfac(z,w)
# print " Retrieved from strongfac, face = ",face
# x = face[0]
# y = face[1]
# print " In fermat: k = ",k," x = ",x," y = ",y," face = "
face
# if face[0] != 0:
# print " index of torial is ",k
# return face
# if k == 0:
# w2 = w
# else:
# w2 = pow(w2,torials[k],z)
# fac = strongfac(z,w2)
# print " "
# print " Could not find factors by strong probable prime test."
Kermit Rose < kermit at polaris.net >
More information about the Tutor
mailing list