[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
Vladimir Shevelev
shevelev at bgu.ac.il
Thu Jul 22 07:41:54 CEST 2010
Of course, one can calculate ord_n(a) by this algorithm ((n,a)=1).
Examples:
to calculate ord_10(3) we have
10+1 0 11
10+11 1 7
10+7 0 17
10+17 3 1
Thus ord_10(3)=1+3=4;
to calculate ord_11(4) we have
11+1 1 3
11+14 0 25
11+25 1 9
11+9 1 5
11+5 2 1
Thus ord_11(4)=1+1+1+2=5.
Regards,
Vladimir
----- Original Message -----
From: Max Alekseyev <maxale at gmail.com>
Date: Wednesday, July 21, 2010 23:05
Subject: [seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> The algorithm iteratively performs divisions by 2 modulo n.
> It starts with n+1 == 1 (mod n) and ends with 1. The total
> number of
> divisions k is then nothing else but the multiplicative order of
> 2 mod
> n.
>
> Max
>
> On Tue, Jul 20, 2010 at 2:18 PM, Vladimir Shevelev
> <shevelev at bgu.ac.il> wrote:
> > Dear Seq Fan,
> >
> > 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.
> >
> > 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/
> >
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
Shevelev Vladimir
More information about the SeqFan
mailing list