I'm A Math Geek
...and I'm also a dreamer. Yes, I realize how much of a longshot this is. If you strike it rich, at least have the courtesy to let me know!
Update (11-Dec-2003): This is version 1.1:
#!/usr/bin/env python
# rsa-640-rand.py:
# RSA-640 Factoring Challenge "Lottery Solution" by Alex Harden
# 09-Dec-2003
# Version 1.1 11-Dec-2003: Eliminated the test against the smaller
# primes and make sure no factors ending with a "5" are attempted.
# Copyright (C) 2003 Alex Harden
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
# Find the GPL online at: http://www.gnu.org/copyleft/gpl.html
# Info about the RSA Challenge Numbers:
# http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
# Interesting fact about the solution to the RSA-576 challenge:
# - both factors were 87 digits (exactly 50% of the number of digits of the
# challenge number's 174)
# RSA-576 numbers: for reference and testing:
# x=18819881292060796383869723946165043980716356337941738270076335642298885971\
# 5234665485319060606504743045317388011303396716199692321205734031879550656996\
# 221305168759307650257059L
# y=39807508642406493739712550055038649119906436234252670840638518957594638895\
# 7261768583317L
# z=47277214610743530253622307197304822463291469530209711645985217113052071125\
# 6363590397527L
# For RSA-640 (193 digits), I'm concentrating on generating random odd numbers
# that have 96-98 digits (est. 319-321 binary digits)
# Let's try to make likely prime numbers using a neat method:
# Reference 1: http://www.maths.abdn.ac.uk/~igc/tch/mx3015/notes/node157.html
# - create random bitstring of 319-321 binary digits (make first and last
# values "1") (v1.1 - eliminate the testing of candidates that end in "5")
# - convert it to decimal long int
# - if it's not divisible by any of the primes < 20000, see if it's a factor of
# RSA-640
# Reference 2: baseconvert.py:
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/111286
# Reference 3: bin2dec: http://pleac.sourceforge.net/pleac_python/numbers.html
# Reference 4: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/162479
########################################
from random import seed, random
import baseconvert
def bin2dec(i):
return baseconvert.baseconvert(i, baseconvert.BASE2, baseconvert.BASE10)
outfile='c:\rsa-640.txt' #if a factor is found, write it here
max=6953607871644L #iterate through the loop this many times then exit
i=0
seed()
x="insert RSA-640 Challenge Number here"L
while i < max:
i+=1
h='1'
pos=0
digits=int(round((2*random())+317,0))
while pos < digits :
if round(random(),0) :
h+='1'
else :
h+='0'
pos+=1
h+='1'
n=bin2dec(h)
if n[-1] <> '5' :
n=long(n)
print 'i=',i
print 'n=',n
z=x%n
if z == 0:
print 'found it'
print 'n=',n
print 'z=',z
file=open(outfile,'a+')
file.write(str(n))
file.write('\n')
file.close()
break
This is version 1.0:
#!/usr/bin/env python
# rsa-640-rand.py:
# RSA-640 Factoring Challenge "Lottery Solution" by Alex Harden
# 09-Dec-2003
# Copyright (C) 2003 Alex Harden
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
# Find the GPL online at: http://www.gnu.org/copyleft/gpl.html
# Info about the RSA Challenge Numbers:
# http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
# Interesting fact about the solution to the RSA-576 challenge:
# - both factors were 87 digits (exactly 50% of the number of digits of the
# challenge number's 174)
# RSA-576 numbers: for reference and testing:
# x=18819881292060796383869723946165043980716356337941738270076335642298885971\
# 5234665485319060606504743045317388011303396716199692321205734031879550656996\
# 221305168759307650257059L
# y=39807508642406493739712550055038649119906436234252670840638518957594638895\
# 7261768583317L
# z=47277214610743530253622307197304822463291469530209711645985217113052071125\
# 6363590397527L
# For RSA-640 (193 digits), I'm concentrating on generating random odd numbers
# that have 96-98 digits (est. 319-321 binary digits)
# Let's try to make likely prime numbers using a neat method:
# Reference 1: http://www.maths.abdn.ac.uk/~igc/tch/mx3015/notes/node157.html
# - create random bitstring of 319-321 binary digits (make first and last
# values "1")
# - convert it to decimal long int
# - if it's not divisible by any of the primes < 20000, see if it's a factor of
# RSA-640
# Reference 2: baseconvert.py:
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/111286
# Reference 3: bin2dec: http://pleac.sourceforge.net/pleac_python/numbers.html
# Reference 4: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/162479
########################################
from random import seed, random
import baseconvert
def bin2dec(i):
return baseconvert.baseconvert(i, baseconvert.BASE2, baseconvert.BASE10)
outfile='c:\rsa-640.txt' #if a factor is found, write it here
max=6953607871644L #iterate through the loop this many times then exit
N = 20000 #generate all primes less than this number
primes=[p for p in range(2,N) if 0 not in [p%d for d in range(2,p)]] #see ref 4
i=0
seed()
x=1353452346357468546835634534L #insert actual challenge number here
while i < max:
bad=0
i=i+1
h='1'
pos=0
digits=int(round((2*random())+317,0))
while pos < digits :
if round(random(),0) :
h=h+'1'
else :
h=h+'0'
pos=pos+1
h=h+'1'
n=long(bin2dec(h))
for b in primes :
if n%b == 0 :
bad=1
break
if not bad :
print "n=",n
z=x%n
if z == 0:
print 'found it'
print "n=",n
print "z=",z
file=open(outfile,'a+')
file.write(str(n))
file.write('\n')
file.close()
break
Comments
Posted by: Scotbuff | December 9, 2003 8:53 PM
Now if there was a BigInteger class for C++, we could really get things cranking.
Posted by: Olu Gerland | December 10, 2003 10:03 AM
Thanks for the interest. I don't do a lot of programming, and Python is my "hobby language". I'd written a weaker version of this script for RSA-576 and hadn't run it in quite a while. When the news broke about RSA-576 having been solved, I regained interest and quickly checked the calculations I was testing in my old script in the Python interpreter. I was happy to confirm that Python was doing the math on such large integers accurately.
So I did a little more research, improved the code (what little there is), and cleaned it up for posting here to see if there was interest.
Any ports you want to share with me are welcome.
I mainly have the "for" loop with the div test against the smaller primes there for completeness, just to see how often the program generates a possibly prime number. The program might run faster if that loop wasn't there; I doubt the z=x%n runs slower than the n%b, which would be the only argument I could see for keeping it.
Update: After posting this I then checked "Olu's" comment for a clue - and he was kind enough to leave his email address... Hey DUDE!
Posted by: aharden | December 10, 2003 11:56 AM
Excellent point regarding the need to check for the primeness of the factor. I removed that check from the Java code, and it is now cranking along at 9400/s.
I'm wondering if we can find a better way than random of generating factors, though. For example, since RSA-640 ends in '9', we know that the two factors either (both end in '3'), or (one ends in '1', one ends in '9'), or (both end in '7').
Hmmm...
Posted by: Xerxes Rens | December 10, 2003 2:04 PM
Posted by: aharden | December 11, 2003 8:53 AM
>Good point about the last digit. But I don't know >if going through the trouble to eliminate guesses >with "5" at the end would buy us much runtime.
I disagree; if the calculation of the modulo op has a time anywhere near that of the random (would have to do some profiling to see if this is true), the speed up would be anywhere from 10-20%. Of course, we could take it much farther than just inspecting the least significant digit. By applying similar constraints to the next most significant digit, we can really start to reduce the number of possibilities. Unfortunately, the next digit is a 0, which doesn't help much at all in base 10. But this brings up the question of why we limit ourselves to doing this analysis in base 10? A similar analysis could be done in
binary:
imagine two binary numbers with 4 digits each:
abcd, and efgh. The least significant digit would be (d & h). The next least significant would be (c & h ) ^ (d & g ). Things get trickier for the next digit, as we now have to worry about carries from the addition of the previous column.
The next least significant digit would be:
(h & b ) ^ (g & c) ^ (f ^ d ) ^ (((c&h)^(d&g)) >> 1) %2
There carry computation doesn't look to elegant, but when compiled, it boils down to 4 very simple assembly ops (two XORS, a bitshift, and one AND),
so computation would be quick. In this way, we could eliminate possible candidates as we generate them. Of course, the number of possibilities would increase polynomially, so we'd have to judge how far to take this, and when to let the random gen take over.
Base 2 is appealing, but then any prime base would give an even distribution of numbers, unlike base 10.
I'll try to get around to posting some code soon.
Posted by: Creight Lersing | December 11, 2003 11:42 AM
The method you're describing might be considered a "number field sieve" method, but I'm not sure. That's the method that was used to factor RSA-576; supposedly you need a lot of horsepower and memory to implement it for integers this large.
I know the method I have here is equivalent to a Gatling gun firing Nerf balls at the earth. ;)
Now that we're getting close to optimizing the "lottery" method, maybe another take on the problem is in order...
Posted by: aharden | December 11, 2003 12:18 PM
Came from a book and was simply to illustrate data types, control structures and functions. Yes, it's lame, but's it's python and my first stab. = )
def greatestCommonDivisor( x, y ):
gcd = min ( x, y )
while gcd >= 1:
if ( x % gcd ) == ( y % gcd ) == 0:
return gcd
else:
gcd -= 1
def determineColor( color ):
if color == "green":
print "You entered green!"
elif color == "purple":
print "You entered purple!"
else:
print "you did not enter green or purple."
number1 = int(raw_input( "Enter a positive integer: " ) )
number2 = int(raw_input( "Enter a positive integer: " ) )
print "The greatest common divisor is", \
greatestCommonDivisor( number1, number2 )
for entry in range( 5 ):
colorchoice = raw_input( "\nEnter your favorite color: " )
determineColor( colorChoice )
Posted by: Shane | December 12, 2003 9:00 AM