mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   New Algorithm - Tester(s) required (https://www.mersenneforum.org/showthread.php?t=5735)

bearnol 2006-04-13 14:18

New Algorithm - Tester(s) required
 
I've just posted the following assertion over at M+2:
[url]http://groups.google.com/group/Mersenneplustwo/browse_frm/thread/539949e8e2560b6b[/url]
Anybody feel like helping me test it?
J

R.D. Silverman 2006-04-13 16:10

[QUOTE=bearnol]I've just posted the following assertion over at M+2:
[url]http://groups.google.com/group/Mersenneplustwo/browse_frm/thread/539949e8e2560b6b[/url]
Anybody feel like helping me test it?
J[/QUOTE]

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

bearnol 2006-04-13 17:33

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

R.D. Silverman 2006-04-13 18:01

[QUOTE=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[/QUOTE]

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.

bearnol 2006-04-13 18:15

(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

R.D. Silverman 2006-04-13 18:30

[QUOTE=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[/QUOTE]

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

ewmayer 2006-04-13 18:57

[QUOTE=R.D. Silverman]WHAT ARE YOU TRYING TO DO??????[/QUOTE]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.

R.D. Silverman 2006-04-13 19:06

[QUOTE=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.[/QUOTE]

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!

bearnol 2006-04-13 19:19

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):
[url]http://bearnol.is-a-geek.com/Mersenneplustwo/Mersenneplustwo.html[/url]
[url]http://www.bearnol.pwp.blueyonder.co.uk/Math/index.html[/url]
]

ewmayer 2006-04-13 19:34

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.

xilman 2006-04-13 20:35

[QUOTE=bearnol]I've just posted the following assertion over at M+2:
[url]http://groups.google.com/group/Mersenneplustwo/browse_frm/thread/539949e8e2560b6b[/url]
Anybody feel like helping me test it?
J[/QUOTE]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


All times are UTC. The time now is 05:40.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.