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

 2006-04-13, 14:18 #1 bearnol     Sep 2005 127 Posts New Algorithm - Tester(s) required I've just posted the following assertion over at M+2: http://groups.google.com/group/Merse...9949e8e2560b6b Anybody feel like helping me test it? J
2006-04-13, 16:10   #2
R.D. Silverman

Nov 2003

22·5·7·53 Posts

Quote:
 Originally Posted by bearnol I've just posted the following assertion over at M+2: http://groups.google.com/group/Merse...9949e8e2560b6b Anybody feel like helping me test it? J
The time to compute 2^n + 1 mod p will be proportional to n (log p)^2
via naiive multiplication methods and n (log p loglogp logloglog p) via
FFT techniques. We only test numbers that are 1 mod 2n. From 2^x to
2^(x+1) there are 2^x/(2n) = 2^(x-1)/n such numbers. Each takes
the amount of time given above. Now multiply.

I do not know where you get the exponent "13".

 2006-04-13, 17:33 #3 bearnol     Sep 2005 127 Posts Thanks for your response, and analysis. However, 1) I fear you have misunderstood what exactly the algorithm does. (and therefore how effective it is) 2) The result quoted is based an empirical one. J
2006-04-13, 18:01   #4
R.D. Silverman

Nov 2003

1CFC16 Posts

Quote:
 Originally Posted by bearnol Thanks for your response, and analysis. However, 1) I fear you have misunderstood what exactly the algorithm does. (and therefore how effective it is) 2) The result quoted is based an empirical one. J
1)
Please correct the misunderstanding. State the algorithm exactly.
My reading of what you wrote is that the algorithm's purpose was to find
small factors of much larger numbers of the form 2^n+1.

2)
If one is looking to analyse an algorithm one starts by determining
its complexity as a function of the input size. Then, and only then
does one try to find explicit constants in place of the implied constants
given by the O() estimates.

 2006-04-13, 18:15 #5 bearnol     Sep 2005 11111112 Posts (thanks again for your response) 1) The source code is there - its complexity is only akin to say, rho method 2) My justification for claim of polynomial (ie logarithmic) speed: a) [the second part of your original analysis] The number of steps required will tend to a constant (sic) b) [the first part ditto] Each step can be performed in polynomial/logarithmic time using 'Russian Peasant' method of exponentiation
2006-04-13, 18:30   #6
R.D. Silverman

Nov 2003

1CFC16 Posts

Quote:
 Originally Posted by bearnol (thanks again for your response) 1) The source code is there - its complexity is only akin to say, rho method 2) My justification for claim of polynomial (ie logarithmic) speed: a) [the second part of your original analysis] The number of steps required will tend to a constant (sic) b) [the first part ditto] Each step can be performed in polynomial/logarithmic time using 'Russian Peasant' method of exponentiation
You still have not stated what computation is being performed.
State the objective(s) of the computation. State the method.
Saying that "it" is akin to Pollard Rho says nothing unless you tell
us what "it" is. WHAT ARE YOU TRYING TO DO??????

2006-04-13, 18:57   #7
ewmayer
2ω=0

Sep 2002
República de California

5×2,237 Posts

Quote:
 Originally Posted by R.D. Silverman WHAT ARE YOU TRYING TO DO??????
If he's trying to get your blood pressure up by way of discussion of his latest vague, dubious claim, he seems to be succeeding.

James (a.k.a. bearnol), if you can't formally justify your asymptotic-complecity claims in a way most reasonable folks can understand, then please be so kind as to at least provide some nontrivial example factorizations, their runtimes, and basic notes about your implementation. I don't want to hear any guff along the lines of "well, I haven't actually *coded* it yet..." or "My implementation uses off-the-shelf-package X, which is, like, totally suboptimal and disguises the true breakthrough speed of the algorithm" - those are the kinds of dodges used by cranks, rogues and scoundrels, i.e. the kinds of people I'm sure you wouldn't want to be seen as keeping company with.

2006-04-13, 19:06   #8
R.D. Silverman

Nov 2003

11100111111002 Posts

Quote:
 Originally Posted by ewmayer If he's trying to get your blood pressure up by way of discussion of his latest vague, dubious claim, he seems to be succeeding. James (a.k.a. bearnol), if you can't formally justify your asymptotic-complecity claims in a way most reasonable folks can understand, then please be so kind as to at least provide some nontrivial example factorizations, their runtimes, and basic notes about your implementation. I don't want to hear any guff along the lines of "well, I haven't actually *coded* it yet..." or "My implementation uses off-the-shelf-package X, which is, like, totally suboptimal and disguises the true breakthrough speed of the algorithm" - those are the kinds of dodges used by cranks, rogues and scoundrels, i.e. the kinds of people I'm sure you wouldn't want to be seen as keeping company with.
A judge would simply dismiss the case for "failure to state a claim"

I am *trying* to be helpful. But the o.p. fails to answer direct questions!

 2006-04-13, 19:19 #9 bearnol     Sep 2005 11111112 Posts 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 ]
 2006-04-13, 19:34 #10 ewmayer ∂2ω=0     Sep 2002 República de California 5×2,237 Posts James - I repeat, please provide some example factorizations and timings. Why should folks who have many demands on their time (that probably includes just about all the ones qualified to judge the veracity of claims such as yours) be bothered to read reams of online documentation unless you provide at least a glimmer of an idea that there may be something to your claim? To put it bluntly: show us some data. Otherwise stop wasting our time.
2006-04-13, 20:35   #11
xilman
Bamboozled!

May 2003
Down not across

23·32·139 Posts

Quote:
 Originally Posted by bearnol I've just posted the following assertion over at M+2: http://groups.google.com/group/Merse...9949e8e2560b6b Anybody feel like helping me test it? J
Here be dragons. Beware.

James' track record so far strongly suggests that anyone who goes any further into his pronouncements deserves all the grief they may get.

That's not to say he hasn't got something. It's only to say that his reputation precedes him.

If (and only if, IMO) he starts to publish rigorous mathematical analysis of his ideas, such analysis to use the language conventional in mathematics, will he be worth taking seriously.

All the above IMAO. YMMV.

Paul

 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 00:48.

Sun Jun 7 00:48:59 UTC 2020 up 73 days, 22:22, 0 users, load averages: 1.42, 1.61, 1.58