find all multiplicands and multipliers for a number

[Steven D'Aprano]

On Sun, 12 Apr 2015 07:34 pm, Brian Gladman wrote:

> On 11/04/2015 03:04, Steven D'Aprano wrote:
> 
>> It may be a bit slow for very large numbers. On my computer, this takes
>> 20 seconds:
>> 
>> py> pyprimes.factors.factorise(2**111+1)
>> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
>> 
>> 
>> but that is the nature of factorising large numbers.
>> 
>> http://code.google.com/p/pyprimes/source/browse/
> 
> I don'tknow how well it compares more generally but where large amounts
> of memory are available a simple sieve works quite well. I have an
> implementation available here (in Python 3):
> 
> http://ccgi.gladman.plus.com/wp/?page_id=1500

Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
factors. I don't think that counts as a simple sieve :-)



> where:
> 
>>>> from number_theory import factors
>>>> print(tuple(factor(2 ** 111 + 1)))
> ((3, 2), (1777, 1) , (3331, 1), (17539, 1), (25781083, 1),
> (107775231312019, 1))
> 
> runs in less than 2 seconds on my laptop.


Although it is not directly comparable to the sieve version I used above, on
my machine I get:

py> import number_theory
py> with Stopwatch():
...     list(number_theory.factors(2**111+1))
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019]
time taken: 5.823970 seconds


so there is a quite good speedup available from using Miller-Rabin. But it's
not a simple sieve any more.

By the way, it is possible to get guaranteed deterministic
(non-probabilistic) results with Miller-Rabin, for small integers. By small
I mean less than 2**64. See my pyprimes for details.



-- 
Steven