Thread: new project ?
View Single Post
Old 2004-06-01, 14:10   #9
xilman's Avatar
May 2003
Down not across

3·5·743 Posts

Originally Posted by junky
when ya meen this number has no known non-trivial factors, do ya meen this number will never been factorised ? it was a most-wanted number, so maybe that's why that number is a bit hard. I'd like to know a bit more about the status of this number please. Will we leave this number at 86.86% complete (6670.29 of 7679 workunits) or we will we reached the 100% too ?

Which methods can we use to find a "non-trivial factor" ?

Wacky corrected my earlier error. The new project is to factor 3^491+1. This number is obviously even, so 2 is a trivial factor. It turns out that the number is actually a multiple of four. After dividing by 4, what remains has 234 decimal digits and it is this one that we are factoring.

A whole bunch of methods can, in principle, find non-trivial factors. Whether they actually find them depends on a number of properties of the factors. If they are small enough, up to 15 digits perhaps, Pollard's rho algorithm should find them. If they are reasonably small, up to 40 digits say, the ECM method has a very good chance of finding them and still stands some chance if they are as big as 50 or 55 digits. That fact that ECM hasn't found any yet suggests that the factors are over 40 digits in size and could well be much larger.

Other methods include the number field sieve and, in principle, quadratic sieve though 234-digit numbers are way beyong what's possible now and, anyway, SNFS will do it much easier. Guess what we are using ...

xilman is offline