mersenneforum.org New Algorithm - Tester(s) required
 Register FAQ Search Today's Posts Mark Forums Read

2006-04-13, 21:09   #12
ColdFury

Aug 2002

26·5 Posts

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
}

 2006-04-13, 21:43 #13 akruppa     "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)
 2006-04-13, 22:22 #14 ewmayer ∂2ω=0     Sep 2002 República de California 101100100011002 Posts 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.")
2006-04-14, 12:39   #15
R.D. Silverman

Nov 2003

22×5×373 Posts

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)

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?

2006-04-14, 16:18   #16
xilman
Bamboozled!

May 2003
Down not across

23×31×41 Posts

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

2006-04-14, 16:32   #17
R.D. Silverman

Nov 2003

22×5×373 Posts

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.

2006-04-15, 18:14   #18
bearnol

Sep 2005

127 Posts

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...

 2006-04-15, 18:43 #19 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
 2006-04-15, 19:06 #20 bearnol     Sep 2005 127 Posts 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
2006-04-15, 19:30   #21
Jushi

Sep 2005
UGent

22·3·5 Posts

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.

 2006-04-15, 19:30 #22 akruppa     "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 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Programming 19 2017-07-16 11:20 houding PrimeNet 14 2015-12-21 09:34 PageFault Software 2 2014-04-14 15:23 Ken_g6 Prime Sierpinski Project 10 2005-01-04 14:36 dave_0273 Hardware 2 2004-06-19 15:34

All times are UTC. The time now is 12:04.

Sun Aug 9 12:04:03 UTC 2020 up 23 days, 7:50, 2 users, load averages: 1.88, 1.69, 1.76