Factorization Questions

From: Raz (faraz.khan_at_ezdoc.net)
Date: 12/24/04 

Date: 23 Dec 2004 23:04:46 -0800

I am not a math student, but I would like to know if the following
methods for factorizing a composite number of at most 2 prime factors
(n=pq), such as in RSA, would work:

Method 1: Genetic Algorithm
0) N is given and is equal to p*q. p & q are very large unknown
primes.
1) Randomly generate a string of digits that represents p and q put
togther, e.g. the string 12345678 mean p=1234 and q=5678.
2) Repeat step 1 several times until you have a large generation of
randoms strings.
3) Evaluate each string by calculating m=p*q. The fitness score of
each string is then the difference |n-m|. If it is 0 then we have
found the factors.
4) Randomly get the two strings with high scores
5) Cross over the two strings to create two offsprings
6) Mutate the offspring and produce and new generation based on the
offsprings.
7) Goto step 3.
8) GA are said to slowly converge to a complete or partial solution

Obviously the fitness function is the most important aspect of this
algorithm. Is the function I have any good?

Method 2: Binary Search
0) N is given and is equal to p*q. p & q are very large unknown
primes. Assume p>q.
1) If p & q are solutions to (x-p)(x-q)=0 then p = (p+q) + SQRT((p+q)^2
- 4*p*q)
2) Replace p+q with m and p*q with n, then the above equation becomes p
= m + SQRT(m^2 - 4*n) and q = m - SQRT(m^2 - 4*n)
3) For p to a valid integer, m^2 > 4*n, i.e. m > 2*SQRT(n)
4) So m lies between 2*SQRT(n) and n.
5) Pick a low point, L=2*SQRT(n), a high point H=n, and a mid point,
M=(L+H)/2.
6) Assume our initial guess of the real m=(p+q) is M.
8) The estimate of p using this guessed value of m is P=M + SQRT(M^2 -
4*n) and Q=M - SQRT(M^2 - 4*n)
7) If our guess for m is higher than the actual value, then P will turn
out to be higher than p.
8) And similary if our guess for m is lower than the actual value, then
P will turn out to be lower than p.
9) Using the values of P & Q from step 8 we calculate N, i.e. our
estimate of n.
10) If N > n then M mst have been bigger than m. m therefore must lie
in the low to mid point range.
11) Thus we repeat from step #5, but this time the new H will the
current mid point.
12) This works just like a binary search.
13) Eventually M will arrive at the correct m, thus revealing the
factors p & q.

I know this doesnt work, but why not? and can it be fixed in some way??

Method 3: Random GCD
0) N is given and is equal to p*q. p & q are very large unknown
primes.
1) Since p & q could be extremely large numbers, a search for them
randomly would be like needle in a hay stack.
2) However, take any multiple of p, e.g. t*p.
3) Then GCD(n, t*p) = p. Similarly GCD(n, s*q) = q.
4) Since t and s can be all numbers from 2 to n-1, and n is extremely
large, it means that the # of multiples of p or q are also very large.
5) So in other words now the problem is not anymore a search of a
single number among trillions & trillsions. It is a search of billions
& billions of numbers among trillions & trillsions. And finding anyone
of them will solve the problem.
6) A search that looks for a number m such that GCD(n, m) <> 1, will
reveal the factors of n.

Is searching for a multiple of p or q any easier than searching for p &
q.

Thanks,
Raz

Relevant Pages

  • Re: Factorization Questions
    ... > primes. ... > 1) Randomly generate a string of digits that represents p and q put ... > randoms strings. ... > 2) However, take any multiple of p, e.g. t*p. ...
    (sci.crypt)
  • Re: As Stakes Increase, Prime-Number Theory Moves Closer to Proof
    ... Prime-Number Theory Moves Closer to Proof ... > contain an arbitrarily-long run of primes. ... desired length of the run, _then_ you can be sure to find a string, ... > An early discovery about the primes was that there is an infinite ...
    (sci.math)
  • doubts as to whether the 3-5-7 exclusive proof is valid or not
    ... Proof that there are no three consecutive primes except 3 5 and 7? ... Now for divisibility by 5, it is obvious that all numbers that end in ... are divisible by 5 so that know there cannot be a string of 5 ...
    (sci.math)
  • Re: Factorization Questions
    ... >> primes. ... >> randoms strings. ... >> 4) Randomly get the two strings with high scores ... >> 5) Cross over the two strings to create two offsprings ...
    (sci.crypt)
  • Re: The 3n+1 Conjecture
    ... string that, given the infinite supply of possible m, can be forced to be arbitrarily long. ... Considering we don't even HAVE an algorithm for producing primes, the same argument can't work for them. ...
    (sci.math)