20060413, 21:09  #12  
Aug 2002
2^{6}·5 Posts 
Quote:
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 } 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 } 

20060413, 21:43  #13 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 aN. 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 20060413 at 22:01 
20060413, 22:22  #14 
∂^{2}ω=0
Sep 2002
República de California
10110010001100_{2} Posts 
Hold on just a minute, Alex: you seem to have forgotten the superduper 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 polynomialtime 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 nonobvious "all integers divisible by primes.") 
20060414, 12:39  #15  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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? 

20060414, 16:18  #16  
Bamboozled!
May 2003
Down not across
2^{3}×31×41 Posts 
Quote:
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 selftaught number theory people do not (by and large) try and sell their inventions to the sick and/or gullible. Paul 

20060414, 16:32  #17  
Nov 2003
2^{2}×5×373 Posts 
Quote:
I just do not understand the psychology of such people. 

20060415, 18:14  #18  
Sep 2005
127 Posts 
Quote:
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... 

20060415, 18:43  #19 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I adivse anyone against spending any nontrivial 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 (N1,p1) 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 
20060415, 19:06  #20 
Sep 2005
127 Posts 
Well you would say that, wouldn't you, Alex  since you're the competition (GMPECM)! :)
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 'wellknown' by anyone other than me... J 
20060415, 19:30  #21  
Sep 2005
UGent
2^{2}·3·5 Posts 
Quote:


20060415, 19:30  #22 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I can't write up a formal analysis until some time in may due to higher priority tasks (yes, including GMPECM), and quite possibly will have other things to do even then. I have analysed the idea of trying different bases for P1 for my thesis, though, and found it utterly useless. IIRC, less than log(B1)/B1 of the possible bases lead to a endofstage1 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help required  ET_  Programming  19  20170716 11:20 
Triple check required  houding  PrimeNet  14  20151221 09:34 
New hardware  help required  PageFault  Software  2  20140414 15:23 
SBprp  a better PRP tester  Ken_g6  Prime Sierpinski Project  10  20050104 14:36 
Sound Card Tester??  dave_0273  Hardware  2  20040619 15:34 