quadratic sieve yet again

1675 days ago by bardg

hugenumber = (2^34)*(3^21)*(5^14)*(7^12)*(11^10) 
       
hugenumber 
       
393776318318112278049301317141449932800000000000000
393776318318112278049301317141449932800000000000000
N = 29097956141 
       
smooth_test_case = 2*5*7*11*3^8 
       
gcd( smooth_test_case, hugenumber ) 
       
5051970
5051970
smooth_test_case 
       
5051970
5051970
def isTwelveSmooth( mynumber ): mygcd = gcd( mynumber, hugenumber ) if (mygcd == mynumber): return true else: return false 
       
isTwelveSmooth( smooth_test_case ) 
       
True
True
isTwelveSmooth( 13 ) 
       
False
False
def pokeAround( base, num_steps = 1000, verbose = false ): found = 0 for j in range(0, num_steps ): temp = base + j square_raw = temp^2 square = (square_raw) % N if (verbose): print temp, print " squares to ", print square, print isTwelveSmooth(square) if (isTwelveSmooth(square)): print temp, print " is a good one." found = found + 1 if (found == 0): print "Sorry, I didn't find anything." 
       
pokeAround( floor(N/2)+10000001, num_steps = 10000000 ) 
       
14560222601  is a good one.
14561896825  is a good one.
14562343760  is a good one.
14566033874  is a good one.
14567281414  is a good one.
14560222601  is a good one.
14561896825  is a good one.
14562343760  is a good one.
14566033874  is a good one.
14567281414  is a good one.
def makeMeSomeData( number ): square_raw = number^2 square = square_raw % N print number, print " squares to ", print square, print " which factors to ", print factor(floor(square)) 
       
makeMeSomeData( 29097947949 ) 
       
29097947949  squares to  67108864  which factors to  2^26
29097947949  squares to  67108864  which factors to  2^26
makeMeSomeData( 29097952045 ) 
       
29097952045  squares to  16777216  which factors to  2^24
29097952045  squares to  16777216  which factors to  2^24
makeMeSomeData( 29097954093 ) 
       
29097954093  squares to  4194304  which factors to  2^22
29097954093  squares to  4194304  which factors to  2^22
makeMeSomeData( 29097955117 ) 
       
29097955117  squares to  1048576  which factors to  2^20
29097955117  squares to  1048576  which factors to  2^20
makeMeSomeData( 103950 ) 
       
103950  squares to  10805602500  which factors to  2^2 * 3^6 * 5^4 * 7^2
* 11^2
103950  squares to  10805602500  which factors to  2^2 * 3^6 * 5^4 * 7^2 * 11^2
magic = 2*(3^3)*(5^2)*7*11 
       
magic 
       
103950
103950
makeMeSomeData( 14550787044 ) 
       
14550787044  squares to  6139546875  which factors to  3^6 * 5^6 * 7^2 *
11
14550787044  squares to  6139546875  which factors to  3^6 * 5^6 * 7^2 * 11
critical_list = [ 14550787044, 14553284322, 14555079185, 14556169339, 14557168255, 14560222601, 14561896825, 14562343760, 14566033874, 14567281414 ] for k in critical_list: makeMeSomeData(k) 
       
14550787044  squares to  6139546875  which factors to  3^6 * 5^6 * 7^2 *
11
14553284322  squares to  1129430400  which factors to  2^7 * 3 * 5^2 *
7^6
14555079185  squares to  37748736  which factors to  2^22 * 3^2
14556169339  squares to  87500  which factors to  2^2 * 5^5 * 7
14557168255  squares to  1058750000  which factors to  2^4 * 5^7 * 7 *
11^2
14560222601  squares to  1572243750  which factors to  2 * 3^3 * 5^5 * 7
* 11^3
14561896825  squares to  10164873600  which factors to  2^7 * 3^3 * 5^2
* 7^6
14562343760  squares to  2028571776  which factors to  2^7 * 3^5 * 7^2 *
11^3
14566033874  squares to  891000000  which factors to  2^6 * 3^4 * 5^6 *
11
14567281414  squares to  339738624  which factors to  2^22 * 3^4
14550787044  squares to  6139546875  which factors to  3^6 * 5^6 * 7^2 * 11
14553284322  squares to  1129430400  which factors to  2^7 * 3 * 5^2 * 7^6
14555079185  squares to  37748736  which factors to  2^22 * 3^2
14556169339  squares to  87500  which factors to  2^2 * 5^5 * 7
14557168255  squares to  1058750000  which factors to  2^4 * 5^7 * 7 * 11^2
14560222601  squares to  1572243750  which factors to  2 * 3^3 * 5^5 * 7 * 11^3
14561896825  squares to  10164873600  which factors to  2^7 * 3^3 * 5^2 * 7^6
14562343760  squares to  2028571776  which factors to  2^7 * 3^5 * 7^2 * 11^3
14566033874  squares to  891000000  which factors to  2^6 * 3^4 * 5^6 * 11
14567281414  squares to  339738624  which factors to  2^22 * 3^4
(2^11)*(3^2) 
       
18432
18432
14567281414 
       
14567281414
14567281414
N - 18432 
       
29097937709
29097937709
gcd( 14567281414 + 18432, N ) 
       
102643
102643
gcd( 14567281414 - 18432, N ) 
       
283487
283487
factor(N) 
       
102643 * 283487
102643 * 283487