       Re: Re: Re: Re: Re: Timing

```Artur wrote:
> Many thanks for Andrzej Kozlowski for this procedure!
> I was execute these on my computer and received follwing Timing
> Table[f[n], {n, 2, 20}] // Timing = 0.071
> Table[f[n], {n, 2, 21}] // Timing = 0.089
> Table[f[n], {n, 2, 22}] // Timing = 525.756
> but increasing limit of n to 23 was catastrophe on my computer (probably
> RAM memory is limit)
>
> Could help me sombody with big memory size computer check these
> procedure for n=23 (next true should occured for n=31)
> Or sombody can explained this catastrophe in relation hardware-software
> relation or estimated how increased time if increased n (is this time
> polynomial time or not)
>
> Best wishes
> Artur

Apparently you wish to replicate

http://www.research.att.com/~njas/sequences/?q=3%2C5%2C7%2C13%2C17%2C19%2C31%2C61%2C89&language=english&go=Search

huge integers, on the order of many millions of bits, just to see if
they are divisible by much smaller integers on the order of perhaps
dozens of bits. This "catastrophe" is entirely self inflicted; you
simply MUST avoid the huge numbers in the first place. Functions like
Mod can be real helpful, in such circumstances.

So you can tackle it as follows. Treat Sqrt as a variable, that is,
use polynomials in x, reduced by x^2-2. Also you want to do reduction
modulo 2^n-1, since all you care about is whether the remainder is zero.
This can be interleaved with powering, for efficiency (avoids huge
numbers/expressions).

Back before version 6 there was an add-on package PolynomialPowerMod
that handled such things, but (I think) was restricted to prime number
moduli. Anyway, I got a bit frustrated trying to figure out how to do
this efficiently using built-in functions in version 6. This is an
admission that either the documentation was lacking, or I was too tired.
Also, I ran afoul of a difficult-to-track crash bug in our development
kernel, and I need to look into that. So I just wrote a bit of code to
do what we need here.

ppMod[poly_, n_, {p2_,m_}] := Module[
{bits=Reverse[IntegerDigits[n,2]], pj=poly, oldpj, res=1},
If [bits[]==1, res = pj];
Do[
pj = PolynomialMod[pj^2, {p2,m}];
If [bits[[j]]==1, res = PolynomialMod[res*pj,{p2,m}]],
{j, 2, Length[bits]}];
res
]

Timing[Map[First,Select[Table[{n, PolynomialMod[
(ppMod[3+2*x,2^(n-1)-1,{x^2-2,2^n-1}] -
ppMod[3-2*x,2^(n-1)-1,{x^2-2,2^n-1}])*(x/8),
{x^2-2,2^n-1}]}, {n,1,1000}], #[]===0&]]]

Out= {158.978, {1, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607}}

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: Re: Player Pro and Packages
• Next by Date: Re: Re: Wolfram User Interface Research? [off-topic!]
• Previous by thread: Re: Re: Re: Re: Timing
• Next by thread: Re: Re: Timing