mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-04-13, 21:09   #12
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

Quote:
Originally Posted by bearnol
WE is an algorithm for factoring (general) integers.
WEP is a faster version that is specific to M+2 integers only.
[there should be sufficient documentation on my website(s):
http://bearnol.is-a-geek.com/Mersenn...neplustwo.html
http://www.bearnol.pwp.blueyonder.co.uk/Math/index.html
]
Here is the pseudo-code of "WE" that I gleaned from the java source:

Code:
Factorize(N) {
 T = 1
 A = 2

 If N < 2, return 1
 If N is divisible by 2, return 2
 If N is a probable prime, return N

 While (A^2 <= N AND (T == 1 OR T == N)) {
   T = GCD(N, (A^N mod N) - A)
   A = A + 1
 }

 If (T > 1 AND T < N)
   Factorize(T)

 return N
}
And here's the pseudo-code for WEP:

Code:
Factorize(N) {
 A = 1
 T = 1
 prime = true
 wanless = 2

 If N < 2 return false
 If N is divisible by 2, return Factorize(N / 2)

 While (wanless < N)
   wanless = wanless * 2

 While ((prime == false AND A^2 <= N) OR (prime == true AND A <= 1000) AND (T == 0 OR T == 1)) {
   T = GCD(N, (A^(N*wanless) mod N) - (A^wanless mod N))
   If (T < N) 
     prime = false
   A = A + 1
 }

 If (T > 1 OR T < N) {
    Factorize(T)
    Factorize(N / T)
 }

 return prime
}
ColdFury is offline   Reply With Quote
Old 2006-04-13, 21:43   #13
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

So he goes through bases a until (a[I]N[/I]-a, N) turns up a factor, that is until 1<(a[I]N[/I]-1-1,N)<N or a|N. For N=2[I]k[/I]+1, it just squares a lot. The much improved WEP algorithm adds the magic "wanless" constant, which is another 2, to the exponent. Can't have too many 2s I guess.

This algorithm combines the probability of success per a examined of trial division with the complexity of a full probable primality test. The complexity to find the factor p should thus be O(p log(N)2 loglog(N)). That's the worst proposed factoring algorithm I've seen in years.

Propz to Bob for keeping his cool, though.

Alex

Last fiddled with by akruppa on 2006-04-13 at 22:01
akruppa is offline   Reply With Quote
Old 2006-04-13, 22:22   #14
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

101100001001012 Posts
Default

Hold on just a minute, Alex: you seem to have forgotten the super-duper asymptotic hypergeometric speedup to be gotten from considering only candidates that are coprime to the initial value of the magic Wanless constant. I'm sure that explains the teensy discrepancy between your analysis and James' claim of polynomial-time factoring.

In any event, let's hope James hasn't yet succeeded in patenting the "magic sequence of Wanless numbers" - otherwise powers of 2 will start coming with hefty license fees. Perhaps James could be indiced to waive the latter, "for the good of all mankind" and so forth. (Or maybe Microsoft beat him to the patent office, with their slightly broader claim on the patently non-obvious "all integers divisible by primes.")
ewmayer is offline   Reply With Quote
Old 2006-04-14, 12:39   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164408 Posts
Default

Quote:
Originally Posted by akruppa
So he goes through bases a until (a[I]N[/I]-a, N) turns up a factor, that is until 1<(a[I]N[/I]-1-1,N)<N or a|N. For N=2[I]k[/I]+1, it just squares a lot. The much improved WEP algorithm adds the magic "wanless" constant, which is another 2, to the exponent. Can't have too many 2s I guess.

This algorithm combines the probability of success per a examined of trial division with the complexity of a full probable primality test. The complexity to find the factor p should thus be O(p log(N)2 loglog(N)). That's the worst proposed factoring algorithm I've seen in years.

Propz to Bob for keeping his cool, though.

Alex

Actually a^N - a should behave as a pseudo random map from Z/NZ --> Z/NZ as a varies.

The "method" is no better (quite a bit worse actually) than just
selecting a random integer less than N and computing its GCD with N.
This is an O(N^(1+epsilon)) algorithm; much worse than trial division.

Please tell me. What is it that compels people who are totally ignorant
of this subject to keep trying to invent their own methods?
R.D. Silverman is offline   Reply With Quote
Old 2006-04-14, 16:18   #16
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2×712 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Please tell me. What is it that compels people who are totally ignorant of this subject to keep trying to invent their own methods?
I'm sure there are a number of reasons.

However, integer factorization is certainly not the only area of study afflicted with such people.

Medicine, for instance, is full of them. The amount of quackery on display is immense. At least the self-taught number theory people do not (by and large) try and sell their inventions to the sick and/or gullible.


Paul
xilman is offline   Reply With Quote
Old 2006-04-14, 16:32   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2016 Posts
Default

Quote:
Originally Posted by xilman
I'm sure there are a number of reasons.

However, integer factorization is certainly not the only area of study afflicted with such people.

Medicine, for instance, is full of them. The amount of quackery on display is immense. At least the self-taught number theory people do not (by and large) try and sell their inventions to the sick and/or gullible.


Paul
And sci.physics has many more cranks/crackpots than sci.math.......

I just do not understand the psychology of such people.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-15, 18:14   #18
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Actually a^N - a should behave as a pseudo random map from Z/NZ --> Z/NZ as a varies.
I don't think it is random, though - there's a helpful bias.
PS I'm still looking for a tester, as the one who initially showed interest dropped out when I told him he might need to run the test for about a year. In his absence I'm doubling up myself, so I would still appreciate a serious offer...
bearnol is offline   Reply With Quote
Old 2006-04-15, 18:43   #19
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I adivse anyone against spending any non-trivial amount of cpu time on this algorithm. How it works is quite clear and well understood, as is the fact that is has no chance of finding a factor of appreciable size (except some rare cases where (N-1,p-1) is very large, and for those there are much better methods). This algorithm is useless, running it on more cpus won't make it any better.

Alex
akruppa is offline   Reply With Quote
Old 2006-04-15, 19:06   #20
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default

Well you would say that, wouldn't you, Alex - since you're the competition (GMP-ECM)! :-)
Neither you nor Bob seemed to know that much about my algorithm when you last posted. I'd be interested to see any technical analysis you might have - I was unaware that this algorithm was 'well-known' by anyone other than me...
J
bearnol is offline   Reply With Quote
Old 2006-04-15, 19:30   #21
Jushi
 
Jushi's Avatar
 
Sep 2005
UGent

22×3×5 Posts
Default

Quote:
Originally Posted by bearnol
PS I'm still looking for a tester, as the one who initially showed interest dropped out when I told him he might need to run the test for about a year. In his absence I'm doubling up myself, so I would still appreciate a serious offer...
One year, are you serious?!? Please tell me this is just a late April Fool's joke.
Jushi is offline   Reply With Quote
Old 2006-04-15, 19:30   #22
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I can't write up a formal analysis until some time in may due to higher priority tasks (yes, including GMP-ECM), and quite possibly will have other things to do even then. I have analysed the idea of trying different bases for P-1 for my thesis, though, and found it utterly useless. IIRC, less than log(B1)/B1 of the possible bases lead to a end-of-stage-1 residue of smaller order than the worst case can have. Btw, providing an analysis of the algorithm would be up to you anyway, especially in the light of your grand claim of polynomial time complexity.

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help required ET_ Programming 19 2017-07-16 11:20
Triple check required houding PrimeNet 14 2015-12-21 09:34
New hardware - help required PageFault Software 2 2014-04-14 15:23
SBprp - a better PRP tester Ken_g6 Prime Sierpinski Project 10 2005-01-04 14:36
Sound Card Tester?? dave_0273 Hardware 2 2004-06-19 15:34

All times are UTC. The time now is 08:00.

Sun Jul 12 08:00:12 UTC 2020 up 109 days, 5:33, 0 users, load averages: 1.14, 1.57, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.