Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: JSH: Upside down situation
Replies: 66   Last Post: Mar 21, 2008 11:05 AM

 Messages: [ Previous | Next ]
 jstevh@gmail.com Posts: 4,535 From: USA Registered: 12/13/06
Re: JSH: Upside down situation
Posted: Mar 16, 2008 2:29 PM

On Mar 16, 10:32 am, rossum <rossu...@coldmail.com> wrote:
> On Fri, 14 Mar 2008 17:06:50 -0700 (PDT), JSH <jst...@gmail.com>
> wrote:
>

> >I am currently working on my own practical implementation of what I
> >call surrogate factoring that follows from the latest theory, and it
> >is pleasingly fast, while I still have to work at getting it to factor
> >really big numbers to my satisfaction. Oh, my stated goal is the
> >ability to factor an RSA encryption sized number in under 10 minutes
> >on a standard desktop.

>
> Have you actually calculated how fast your current method would be on
> a 500 bit RSA number James?
>
> I posted some timings:
>
> Average timings over 200 numbers:
> 20 bits: 2.265 mSec average per number. 0 misfactors.
> 22 bits: 10.310 mSec average per number. 0 misfactors.
> 24 bits: 12.345 mSec average per number. 0 misfactors.
> 26 bits: 50.155 mSec average per number. 0 misfactors.
> 28 bits: 294.765 mSec average per number. 0 misfactors.
>
> We can use those timings to do a rough back-of-an-envelope calculation
> of how long it would take to factor a 500 bit RSA number.

Except your technique isn't the full surrogate factoring as I've
explained repeatedly to you.

Here's output from my current program, and again I ask that you post
YOUR timings for this particular number.

This time it is incumbent of you to do so as your posting could be
taken as an attempt at convincing others against the theory.

And my research program still is not optimized as I continue to
methodically work through issues, as it's still way too slow, but I'm
still solving big problems in terms of practical implementation.

It took 10 seconds for this still relatively small number. Now what

Example 20484149553887:

n=1
f_1.mod(p)=259
f_2.mod(p)=483
alpha*k mod(p)=182
alpha^{-1}*(1+a^2)k mod(p)=235

k_0=196616
k=285340
alpha=23

maxPrime=619

k_0/p=317
steps=12

Total all combinations: 487652
Time: 4454
Time/combination: 0.009133562458474485

Surrogate:
( 3 )( 7 )( 619 )( 34033 )( 51239 )
Product: 22667875714113

Surrogate combinations checked: 5708
Initial Factorization:

f_1=214433
f_2=95527039
Now checking its factors...
Success!
Factors:
( 214433 )( 95527039 )
Product: 20484149553887

In coming is 20484149553887

Surrogate factorization data for target:

Surrogates factored : 430
Surrogates not factored : 9
Factored fuel percentage: 97%

Processing time: 10328
Number of digits: 14
bitLength=45

***************************************************

You posted timings rossum and made an extrapolation against an RSA
number.

Now post timings with your code for 20484149553887.

Or concede that you're talking out of your ass.

James Harris

Date Subject Author
3/14/08 jstevh@gmail.com
3/14/08 mensanator
3/14/08 jstevh@gmail.com
3/14/08 drtek
3/14/08 Ryugyong Hotel
3/14/08 jstevh@gmail.com
3/15/08 drtek
3/15/08 mensanator
3/15/08 Jesse F. Hughes
3/15/08 Vend
3/15/08 jstevh@gmail.com
3/15/08 David Bernier
3/16/08 rossum
3/16/08 Michael Press
3/16/08 MTBrenneman@gmail.com
3/17/08 Michael Press
3/17/08 Michael Press
3/16/08 mensanator
3/17/08 MTBrenneman@gmail.com
3/17/08 Michael Press
3/18/08 Tim Little
3/17/08 MTBrenneman@gmail.com
3/18/08 Tim Little
3/20/08 Pubkeybreaker
3/17/08 Rotwang
3/17/08 Michael Press
3/17/08 drtek
3/18/08 rossum
3/18/08 Randy Poe
3/18/08 rossum
3/18/08 jstevh@gmail.com
3/19/08 Michael Press
3/18/08 mensanator
3/19/08 Tim Smith
3/20/08 Pubkeybreaker
3/16/08 jstevh@gmail.com
3/16/08 rossum
3/17/08 jstevh@gmail.com
3/17/08 Canaan Banana
3/17/08 MTBrenneman@gmail.com
3/17/08 Marshall
3/17/08 drtek
3/17/08 litsohate@yahoo.com
3/16/08 Vend
3/17/08 Rupert
3/17/08 rossum
3/18/08 jstevh@gmail.com
3/19/08 David Bernier
3/19/08 rossum
3/19/08 jstevh@gmail.com
3/19/08 Rotwang
3/19/08 rossum
3/19/08 jstevh@gmail.com
3/19/08 drtek
3/20/08 rossum
3/19/08 Pubkeybreaker
3/19/08 rossum
3/19/08 Phil Carmody
3/20/08 Pubkeybreaker
3/20/08 drtek
3/21/08 rossum
3/19/08 tinyurl.com/uh3t
3/21/08 jstevh@gmail.com
3/21/08 drtek