in reply to Vampire Numbers
38^2=3^2 (mod 1435)
It is trivial to then check if the factor (38+3 in this case) is a permutation of n/2 digits from the original number.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Factors
by kvale (Monsignor) on Jun 12, 2002 at 21:01 UTC | |
| [reply] |
by gumby (Scribe) on Jun 12, 2002 at 21:45 UTC | |
O(e^(sqrt(1.125ln(n)ln(ln(n))))) But with certain improvements (such as using Wiedemann's Gaussian Elimination algorithm over GF(2)), it's running time is given by O(e^(sqrt(ln(n)ln(ln(n))))) The Number Field Sieve is better for numbers over 100-digits and has running time O(e^(1.9223((ln(n))^1/3(ln(ln(n))))^2/3)) Excuse my notation (but TeX would be overkill). Note: O(stuff) means the magnitude of the running time is < A * stuff for some constant A and all values of n. | [reply] |
by YuckFoo (Abbot) on Jun 12, 2002 at 22:30 UTC | |
Program correctly factors 24 to 4*6 and 2*12 but misses 3*8. Program finds no factors for 54. YuckFoo Update: With a little thought one can see the program will only find factor pairs that are both even or both odd. x+y * x-y = p.
| [reply] [d/l] |
by kvale (Monsignor) on Jun 13, 2002 at 04:51 UTC | |
For 54, this yields But this code is unsatisfying because it takes longer than the simple trial by division. Thinking from a divide and conquer point of view, it is probably faster to use these methods to find a factorization, then recursively find factorizations of the factors untill all are prime. -Mark | [reply] [d/l] [select] |
by gumby (Scribe) on Jun 13, 2002 at 15:43 UTC | |
| [reply] [d/l] |
by gumby (Scribe) on Jun 15, 2002 at 19:21 UTC |