#!/usr/bin/env python

# rsa-704-rm.py:
# RSA-704 Factoring Challenge "Rabin-Miller Solution" by Alex Harden
# Version 1.0: 20-Apr-2006

# Copyright (C) 2006  Alex Harden (http://alexharden.org/blog/)

# 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 solutions to the RSA-576 and RSA-640
# challenges: both factors were 50% of the number of digits of the
# challenge number's total digits. (Both binary and decimal.)

# RSA-576 numbers: for reference and testing:
# x=18819881292060796383869723946165043980716356337941738270076335642298885971\
# 5234665485319060606504743045317388011303396716199692321205734031879550656996\
# 221305168759307650257059L
# y=39807508642406493739712550055038649119906436234252670840638518957594638895\
# 7261768583317L
# z=47277214610743530253622307197304822463291469530209711645985217113052071125\
# 6363590397527L

# RSA-640 numbers:
# x=31074182404900437213507500358885679300373460228427275457201619488232064405\
# 1808150455634682967172328678243791627283803341547107310850191954852900733772\
# 4822783525742386454014691736602477652346609L
# y=16347336458092538484431338838650908598417836700330923121811108523893331001\
# 04508151212118167511579L
# z=19008712816648221131268515739354139754718967899685154936666385390880271038\
# 02104498957191261465571L

# For RSA-640 (193 digits), I concentrated on generating random odd numbers
# that had 96-98 digits (est. 319-321 binary digits).  The solution numbers 
# each had 97 digits and were each 320 binary digits (the middle of the
# estimated range).

# For RSA-704 (212 decimal digits), I'm concentrating on generating 
# numbers that have 352 binary digits. (106 decimal digits)

# Reference 1: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/410681
#  - saved the script as rabin_miller.py in my python/lib directory
#  - using the generate_prime method to generate possible primes; my
#    "lottery" script generates numbers randomly, not algorithmically
########################################

import rabin_miller

outfile='./rsa-704.txt'  #if a factor is found, write it here
bits=352
x=74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359L
z=1
i=0
while z <> 0 :
    i+=1
    n=rabin_miller.generate_prime(bits)
    z=x%n
    print "i=",i
    print "n=",n
    print "z=",z
    print "-----------"
    if z == 0 :
        print 'found it'
        print 'factor1=',n
        print 'factor2=',x/n
        print 'challenge=',x
        file=open(outfile,'a+')
        file.write(str(n))
        file.write('\n')
        file.close()
        break