Re: JSH: What is surrogate factoring? Once more.

On Sep 7, 6:05?pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Fri, 07 Sep 2007 14:32:59 -0700, marcus_b





<marcus_bruck...@xxxxxxxxx> wrote:
On Sep 7, 6:07 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Fri, 07 Sep 2007 01:39:19 -0700, mike3 <mike4...@xxxxxxxxx> wrote:
On Sep 4, 3:13 am, riderofgiraffes <mathforum.org...@xxxxxxxxxxxxxx>
wrote:
Distilling out the text, and leaving just the
description of the method, you seem to have this.

Let T be the number to factor, and suppose that
x and y (unknowns) are such that x^2 = y^2 (mod T)

If we can find x and y then we have factored
T, although possibly trivially.

How does one use x and y to factor T, anyway?

x^2 = y^2 mod T

x^2 - y^2 = 0 mod T

(x+y)(x-y) = 0 mod T

Try GCD(x+y, T) and GCD(x-y, T) to see if any interesting factors of T
turn up.

This is the basis of Fermat's method, Dixon's method and the Quadratic
Sieve as well as James' method.

rossum

True, this is the basis for Fermat's, Dixon's, and the Quadratic
Sieve
method. However as I have pointed out in a previous reply to you and
in
other posts, it is a major problem with Harris's method that his
algorithm
for computing x and y does NOT usually lead to

x^2 = y^2 mod T.

In Harris's examples and even in your own examples of successful
Harrisian surrogate factoring, the equation x^2 = y^2 mod T is usually
not
satisfied. See, e.g., your post of August 31 in the thread
'Surrogate
factoring, periodic behavior', or your post of September 4 in this
thread
regarding the factorization of 400.

Indeed, the way Harris presents his idea, ending up with this
equation
would seem to be his main objective. Somewhere along the line he
forgets
this. If his algorithm could force x^2 = y^2 mod T in a high
percentage
of cases (as, e.g., Dixon's algorithm does), he would have something
worthwhile. As it is, his surrogate factoring method rarely results
in
x^2 = y^2 mod T. In my view this explains why his method does not
perform
much if any better than random GCD.

Marcus.

Agreed. I was describing James' method, as presented by James - warts
and all.

His problem is that he does not yet have a way of picking k or n that
performs any better than random - so in general his values of k do not
result in a useful value of x (or y).

As you say he seems to forget that he makes an assumption about k at
the start and then never returns to it after - picking k apparently at
random rather than working from his initial k = 2x mod T. His
difficulty is that he has not found a way to determine probable values
for x, and hence of k. Until he can do that, his method is likely to
perform badly.

rossum- Hide quoted text -

- Show quoted text -
--------------------------------------
Given an odd composite T
A Surrogate, S is defined as:

S = 2*k^2 + n*T
where k and n are nonzero integers

If a factor p of T is known, then
the factor A, of S is:

A=m*p+k
where m is a nonzero integer

Then n = MOD(MOD(2*k^2,A)*(A-ZInvMod(B,A)),A)

where ZInvMod(B,A) = X such that B*X mod A = 1
and B = MOD(T,m*p+k) = MOD(T,A)

n is periodic and is in general, with J an integer:

n' = A*J + n

So, S having the factor A can be written as:

S' = 2*k^2+(A*J+n)*T
-------------------------------------------------------
If no factor of T is known, then
a factor A of some S can be generated and n
calculated using that A and a suitable k.
Then S = 2*k^2 +n*T will produce the S
having that A as a factor. Then GCD(T,A-k)
may factor T.
Instead of picking S and struggling with its
factorization, it's factor is just declared and
the S it factors can be found, saving work.

For the case of k = 1,
if A is a power of 2
then A-k may have a factor in common with T.
If A > T, A may be replaced with MOD(A,T)
and n calculated with the more reasonable sized A:

n = MOD(MOD(2*k^2,A)*(A-ZInvMod(B,A)),A)
using B = MOD(T,A)

and

S' = 2*k^2+(A*J+n)*T

If A - k shared a factor with T when A was a power of 2,
it will still share the same factor with T after the substitution.

This is the basis for the following factoring program:
Given T to be factored

1) pick A = the square of 2,3,5,7,11, ...(Choose one)
2) calculate n and S with k = 1
3) verify that A divides S
4) Try GCD(T,A-k)
5) If no factor of T is found, increment the exponent and go to 2)
5a) If it goes on too long, choose another from 2,3,5,7,11, ...
and go to 2)
(T = 2047 shows one reason for this)
(T = 8225489 shows another reason for this)

Other methods to systematically choose A exist.
One such is A = c^(x!) using MOD(A,T) as before.

You can get anything you like as a factor of S as long
as its coprime to T.

Enrico


Window Script file below. To use, copy everything below the
dashed line to a text editor. save the text file but give it a .vbs
extension instead of .txt. Or save as a .txt file and rename it
as a .vbs file. (Note-comments are preceeded by a single quote)

To view & edit the .vbs file, right click and choose edit. To save
changes, click file, save (control-s) and the .vbs file will be
updated from your open text file.

To run the script file, double click the filename or right click it
and choose open.

If you modify the code and get stuck in a loop, use
alt Ctrl Delete to bring up the task manager, click the processes
tab, select wscript.exe and click the end process button.
Warning message can be ignored since wscript.exe was
started by you when you ran the script.

Safest bet is to write your own code.
-----------------------------------------------------------------------------------

'Enrico's Souped - Up Surrogate Factoring Method

'Its not really a cheat because this routine works by
'picking factors of S that are known to exist for some n

dim X,Y,Z,c,e,f,p,T,I,p1,p2,k,gcd
dim g 'g is a factor of S for some n
dim base 'Factors of S will be base^x
base = array(2,3,5,7,11) 'will try five bases

T=inputbox("Odd T = ?") 'Enter target to be factored
gcd=0 'Initialize gcd counter
k=1 'Use k=1 with all S=2*k^2+T
e = 2 'Start with base^2

for I=0 to 4 'Can try all 5 bases
msgbox("pass # "&I+1) 'Indicates progress thru bases
f=base(I) 'load base for trial factor of S
msgbox("using powers of "&f) 'Indicates which base is in use

call main 'Try c=500 max values of factors of S
next
msgbox("all bases used. Check if T is prime") 'Failed to factor T

sub main()
c=500 'Maximum 500 trials per base
do 'Generate powers of base = factors of S
f=f mod T 'f is a factor of S for which n could be calculated
g=f 'Save current value of f
g=g-k 'Factor of Surrogate minus k. Check for factor of T

X=g 'Preserve value of g
Y=T 'Preserve value of f
do 'do GDC(X,Y)
Z = X Mod Y
if Z = 0 Then exit do 'GCD found
X = Y: Y = Z
loop while Z<>0

gcd=gcd+1 'Increment gcd counter
call fusco 'Evaluate GDC found
f=base(I)*f:c=c-1:e = e + 1 'Next power of base, loop control, and
exponent
loop while c>0
if c=0 then msgbox("Iteration Limit Exceeded - Check if "&T&" is
prime")
e=2 'Set exponent back to starting value
end sub

sub show()
msgbox("Factors of "&T&" : "&Y&" * "&T/Y)
msgbox("Exponent = "&e)
msgbox("Number of GCD's = "&gcd)
Wscript.quit
end sub

sub altshow()
msgbox("T="&T&" is in 2^"&e&" -1"&" ***Trying next
base***"&VbCrLf&"Check for Primality first")
msgbox("Exponent = "&e)
msgbox("Number of GCD's = "&gcd)
msgbox("trying next base")
end sub

sub fusco()
if Y=1 then exit sub 'Try next higher power of base
if Y - T = 0 then call altshow:c=0:exit sub 'Factor is same as T. Try
next base
if Y>1 then call show:c=0:exit sub 'Factor of T found - Display
results
end sub 'Return to main

.

Loading