[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
Georgi Guninski
guninski at guninski.com
Wed Jul 21 11:02:16 CEST 2010
your algorithm seems correct for odd numbers up to 20000.
looks like if you replace "+m(i-1)" with "-m(i-1)" the result is either the mult. order or half the mult. order.
i wonder can you work "backwards" to find n with prescribed multiplicative order of 2 (this is divisor of phi(n) ) ?
attached is a pari implementation.
On Tue, Jul 20, 2010 at 06:36:12PM +0000, Vladimir Shevelev wrote:
> Dear SeqFans,
>
> I would like to present an easy (till now-conjectural!) algorithm of calculation of multiplicative order of 2 mod n (n arbitrary positive odd number). It is based on trivial calculation of A007814(x) in base 2.
>
> Step1. l(1)=A007814(n+1), m(1)=(n+1)/2^l(1);
> Step i(i>=2). l(i)=A007814(n+m(i-1)), m(i)=(n+m(i-1))/2^l(i);
> The process ends when m=1 (say, m(k)=1).
>
> Now we have: A002326(n)=l(1)+...+l(k).
>
> Example (here A007814=a(n)).
>
> a(17+1)=1, (17+1)/2=9;
> a(17+9)=1, (17+9)/2=13;
> a(17+13)=1, (17+13)/2=15;
> a(17+15)=5, (17+15)/(2^5)=1.
>
> Thus A002327(17)=1+1+1+5=8.
>
> Regards,
> Vladimir
>
> Shevelev Vladimir
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
-------------- next part --------------
{
shev(n,sig=1)=
/*
(till now-conjectural!) algorithm of calculation of multiplicative order of 2 mod n (n arbitrary positive odd number).
sig is 1 (original Shevelev) or
-1 (modified, can return half the multiplicative order)
Date: Tue, 20 Jul 2010 18:36:12 GMT
From: Vladimir Shevelev <shevelev at bgu.ac.il>
To: seqfan at list.seqfan.eu
*/
local(res,m1,l1);
if(n%2==0,return(0));
l1=valuation(n+1,2);
m1=(n+1)/2^l1;
res=l1;
while(m1>1,
l1=valuation(n+sig*m1,2);
m1=(n+sig*m1)/2^l1;
res += l1;
);
return(res);
}
More information about the SeqFan
mailing list