mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-06-10, 04:04   #23
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

Quote:
Originally Posted by VJS
I do agree with you however that the RSA challenges are a waste of computing power. Most of these challenges can be solved with simple stats.

I.e. It would take x computers y years to compute z itterations with program ??? to crack the key.

Who really cares what the two factors are in the long run, but this could be said about alot of the projects we are doing.
What simple stats solved RSA-576 ?
None, It was an actual run of GNFS that solved it.
It required people, software, hardware, mathematical
understanding, programming skill, time to solve it.

It is the continued effort of skilled mathematicians
and programmers over many years that have resulted
in the current factoring methods.

A reason to care about the challenges is the security
of RSA numbers used for encrypting real information.

The various math projects have value in multiple ways.
They promote testing the assumptions and limits
of current algorithms and the developing of new ones,
the study of more advanced mathematical methods
to create better/more effective systems of factoring
with improved math libraries and tools.

They expose many people to the richness of mathematical
fields with the possibility of getting a general idea behind
the process of solving the particular problem.

Without the various projects, I would not have known of the
existance of the various factoring methods that are/have been employed.
They have lead me to this forum and to search various math sites
for more information about the math these programs employ.

I have tried to implement some of the algorithms, with varying
amounts of success, and I keep trying, but I continue to learn by reading
what people with much more mathematical knowledge and skill
than I are posting and then lookup further information at math
reference sites.
dsouza123 is offline   Reply With Quote
Old 2005-06-10, 04:41   #24
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by jasonp
D.J. Bernstein has some neat ideas about accelerating the CF algorithm, but those ideas can also be applied to the sieve-based methods.
When googling for bernstein continued fraction I stumbled upon a paper by Franke and Kleinjung. Sounds very interesting, they describe their improved approach to lattice sieving.

Is there any chance that lattice sieving would speed up MPQS?

Alex
akruppa is offline   Reply With Quote
Old 2005-06-10, 07:24   #25
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

73×151 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Allow me to also point out that once one has done about 10^48 such
trial divisions, one will start to repeat divisions already done. (i.e.
get collisions). The number of such collisions rises rapidly as the algorithm
progresses until almost all divisions performed are repeats of earlier divisions.
There are (2^320 - 2^319)/2 odd 320 bit numbers. (~ 5 x 10^95)
Even if you do this number of divisions, you will miss out on testing
about 1/e ~ 36% of the numbers.
Thanks Bob!

See, I knew you could post something of value to most readers here if you answered the questions as asked, even though the questions indicated a certain hopeless naivety.


Paul
xilman is offline   Reply With Quote
Old 2005-06-10, 12:05   #26
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

Quote:
Originally Posted by akruppa
When googling for bernstein continued fraction I stumbled upon a paper by Franke and Kleinjung. Sounds very interesting, they describe their improved approach to lattice sieving.

Is there any chance that lattice sieving would speed up MPQS?
Thanks Alex, I was hoping a paper like this was available somewhere. Franke's code has a TeX description of the same stuff.

The ideas I was referring to was Bernstein's paper "How to Find Small Factors of Integers", available at http://cr.yp.to/papers.html#sf

jasonp
jasonp is offline   Reply With Quote
Old 2005-06-10, 16:28   #27
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Angry ECM sigma

Quote:
Originally Posted by R.D. Silverman
Allow me to also point out that once one has done about 10^48 such
trial divisions, one will start to repeat divisions already done. (i.e.
get collisions). The number of such collisions rises rapidly as the algorithm
progresses until almost all divisions performed are repeats of earlier divisions.
There are (2^320 - 2^319)/2 odd 320 bit numbers. (~ 5 x 10^95)
Even if you do this number of divisions, you will miss out on testing
about 1/e ~ 36% of the numbers.
A good point. Incidentally, it has always disturbed me that GMP-ECM only generates 32-bit random sigmas, as we are then likely to hit repeats after about 216 ~= 65,000 curves. Moving to 64-bit random sigmas like prime95 uses would make this a lot less likely to happen. Does this keep anyone else up at night, or am I the only one?

Sam
trilliwig is offline   Reply With Quote
Old 2005-06-10, 17:06   #28
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by trilliwig
A good point. Incidentally, it has always disturbed me that GMP-ECM only generates 32-bit random sigmas, as we are then likely to hit repeats after about 216 ~= 65,000 curves. Moving to 64-bit random sigmas like prime95 uses would make this a lot less likely to happen. Does this keep anyone else up at night, or am I the only one?

Sam
You are correct.

However, it is a theoretical concern only because noone has come close to running 65K curves on a single number. And a small number of collisions
is only a very slight loss in efficiency.

As machines get fast enough to let us run 65K curves, then we will indeed
need to use 64 bit seeds
R.D. Silverman is offline   Reply With Quote
Old 2005-06-10, 20:40   #29
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Torbjorn Granlund suggested allowing larger sigma values in late 2003. This was my reply:

Quote:
Torbjorn Granlund wrote:

> I indend to compile new binaries when I find some time.
>
> Having a larger set of values to draw our random sigma from would be
> desirable. The problem is: where do we find the source of randomness?
> Generating ever so large sigma values doesn't help if we seed with
> gettimeofday, with ist accuracy of about 40-bits.



A larger set of sigma values is not really urgent, I think. With 2^32 values to choose from, the probability of a collision is 1/2 at about 77000 samples. When testing to p55 by the old scheme (B2=100*B1) we do about 86000 curves, the expected number of collisions is 0.86 there. Even when testing to p60 with a total of 210000 curves done, the expected number of collisions is only 5.1, so there will be a few, but the loss of cpu time is <0.0025%.

The new scheme with higher B2 values uses fewer curves so sigma collisions should be even less of a problem.

We could just use larger sigma values (getting more bits out of mpz_urandomb) nonetheless, seeding with /dev/[u]random on systems that have it, otherwise seeding with something that gives us at least 32 bit resolution. That should be sufficient.

In large runs on different input numbers the same sigma may appear twice (as Bruce observed), but using the same sigma on different numbers is just fine. The generated groups are totally different.

The only thing I'm really concerned about is seeding from sources that tend to always produce the same values. I believe we had a problem like that with getpid() under Cygwin when writing ecm 5.0.

Alex

Last fiddled with by akruppa on 2005-06-12 at 12:20 Reason: B1<->B2
akruppa is offline   Reply With Quote
Old 2005-06-10, 21:11   #30
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22·5·17·19 Posts
Default

I assume that 64-bit CPUs generate 64-bit random numbers. If so, then it is even probably less of an issue. Bruce Dodson runs many of his curves on a 64-bit AMD. I would not be surprised if many others use 64-bit machines for large B1s.
rogue is online now   Reply With Quote
Old 2005-06-10, 21:31   #31
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

The register size of the cpu has nothing to do with it. The question is:
(1) how large must the range for the sigma values be that in practical application the efficiency loss due to sigma collisions is negligible
(2) where do we find enough entropy to seed the RNG for generating such sigma values

For the time being and the forseeable future, 32 bit sigmas are quite sufficient and easy to seed even on systems that don't feature a /dev/urandom device.

Incidentally, does someone know of a simliar source of entropy under Windows? Is there a system call or something?

Alex
akruppa is offline   Reply With Quote
Old 2005-06-10, 22:23   #32
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23·7·137 Posts
Default

Quote:
Originally Posted by akruppa
Incidentally, does someone know of a simliar source of entropy under Windows? Is there a system call or something?
Prime95 uses the C rand function for 16 bits and the low 32 bits of the chip's timestamp counter. I think it gets the remaining 5 bits (to make a 53-bit double) from another call to the rand function.
Prime95 is offline   Reply With Quote
Old 2005-06-11, 06:12   #33
cjohnsto
 
Jun 2005

11112 Posts
Default

Probably the best source of randomness for windows is from the CryptGenRandom function. It is supposed to be used for random seeds, IVs, chanlenges, etc in cryptographic circumstances.
cjohnsto is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Challenge on the net devarajkandadai Miscellaneous Math 0 2012-05-31 05:17
When I was your age.....CHALLENGE petrw1 Lounge 14 2009-11-23 02:18
Challenge science_man_88 Miscellaneous Math 229 2009-09-07 08:08
Another challenge R.D. Silverman Programming 24 2005-07-27 21:08
Who is Challenge? JuanTutors PrimeNet 2 2004-07-22 12:56

All times are UTC. The time now is 18:07.


Sun Nov 28 18:07:56 UTC 2021 up 128 days, 12:36, 0 users, load averages: 0.79, 0.95, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.