Re: Surrogate factoring, theory versus implementation

From: Michael Brown (see_at_signature.below)
Date: 01/24/05 

Date: Tue, 25 Jan 2005 08:02:06 +1100

jstevh@msn.com wrote:
[...]

Repeating from an earlier post that probably got lost in the morass of other
posts:

[[BEGIN REPEAT]]

For what it's worth, I cooked up a couple of ~64-bit primes (was a 104-bit
product, I forgot to set the uppermost bits). They weren't specially chosen
or even well-generated. I just used the rand() function to generate a binary
string. Their product was 17417537469613251264524569748998981537. "factor"
from:
http://www.asahi-net.or.jp/~KC2H-MSM/cn/
factored it in 33.26 seconds (1128714656609730623 * 15431302648208293919).
After a bit of trial and error, it turned out that it could factor the
product squared minus 16 in 3.26 seconds:
303370611505381579716912725262028356146608169452120680027239449463266882353
= 3* 3 * 71 * 307 * 2673397 * 84828952219129 * 8533686513259849 *
799079573776815674841701598797953

How do you get the original primes from the above factorisation? Or does j
have to be specially chosen?

[[END REPEAT]]

And I followed up with:

[[BEGIN REPEAT]]

Michael Brown wrote:
[...]
> How do you get the original primes from the above factorisation? Or
> does j have to be specially chosen?

>From what I can gather, it's supposed to go something like:
  b_i = factors of j^2 ( = 16 in this case)
  f_i = factors of T (product squared minus j^2)

  b_1 = product of some subset of b_i
  b_2 = -j^2 / b1
  f_1 = product of some subset of f_i
  f_2 = T / f_1

  A = some integer (not sure how to calculate this)

Then a possible factor is:
  (b_1 f_2 + b_2 f_1 + 2 j^2) / A

Since I'm not sure how to calculate A, I just calculated each possibility
mod each of the original primes to see if it was zero. No such combination
occured (except for the trivial cases b_1 = f_1 = 1 or the prime to be
tested was zero).

Is my interpretation correct?

[[END REPEAT]] 

-- 
Michael Brown
www.emboss.co.nz : OOS/RSI software and more :)
Add michael@ to emboss.co.nz ---+--- My inbox is always open

Relevant Pages