mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-04-13, 14:18   #1
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default 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
bearnol is offline   Reply With Quote
Old 2006-04-13, 16:10   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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".
R.D. Silverman is offline   Reply With Quote
Old 2006-04-13, 17:33   #3
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

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
bearnol is offline   Reply With Quote
Old 2006-04-13, 18:01   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-13, 18:15   #5
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

(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
bearnol is offline   Reply With Quote
Old 2006-04-13, 18:30   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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??????
R.D. Silverman is offline   Reply With Quote
Old 2006-04-13, 18:57   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

263768 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-04-13, 19:06   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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!
R.D. Silverman is offline   Reply With Quote
Old 2006-04-13, 19:19   #9
bearnol
 
bearnol's Avatar
 
Sep 2005

11111112 Posts
Default

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
]
bearnol is offline   Reply With Quote
Old 2006-04-13, 19:34   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·13·443 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-04-13, 20:35   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24×641 Posts
Default

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
xilman 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 15:02.

Sun Sep 27 15:02:17 UTC 2020 up 17 days, 12:13, 1 user, load averages: 2.15, 1.53, 1.38

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.