#!/usr/bin/env python

# rsa-704-rand.py:
# RSA-704 Factoring Challenge "Lottery Solution" by Alex Harden
# Version 1.1: 20-Apr-2006

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

# Thanks to Phil Kilinskas for suggesting the use of the native
#  getrandbits() function.

# 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 
# random odd numbers that have 352 binary digits. (106 decimal 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 352 binary digits (make first and last
#   values "1")
# - convert it to decimal long int
# - if it's not divisible by any of the primes < 2000, see if it's a factor
#   of RSA-704  (this step is optional - not sure how expensive the "z=x%n"
#   actually is)

# Reference 2: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/162479

########################################

from random import seed, getrandbits

outfile='./rsa-704.txt'  #if a factor is found, write it here
i=0
digits=352
N=2000
primes=[p for p in range(2,N) if 0 not in [p%d for d in range(2,p)]]
z=1
seed()
x=74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359L
while z <> 0 :
    i+=1
    n=getrandbits(digits)
    n |= (1  <<  (digits-1))
    checkme=1
    for p in primes :
        if n%p == 0 :
            checkme=0
            break
    if checkme :
        z=x%n
        if i%500 == 0 :
            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()