[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n

[Robert Gerbicz]

2010/7/21 Alexander P-sky <apovolot at gmail.com>

> So somewhat contrary to Charles Greathouse there may be scientific
> (not computational) interest in the method itself (beyond finding
> interesting properties).
>
> On 7/21/10, Georgi Guninski <guninski at guninski.com> wrote:
> > what suprises me is the algorithm doesn't use any modular stuff mod n ...
> >
> > with a C program checked both versions to close to a million - no
> > counterexamples found.
> >
> > On Wed, Jul 21, 2010 at 10:21:20AM -0400, Charles Greathouse wrote:
> >> It's worth noting that the algorithm (implemented, as below, as a
> >> script) is about 300 times slower than the built-in znorder(Mod(2,n))
> >> for 4-digit numbers and about 1500 times slower for 5-digit numbers.
> >> So the interest in the method is in finding interesting properties, as
> >> Georgi suggests.
> >>
> >> Charles Greathouse
> >> Analyst/Programmer
> >> Case Western Reserve University
> >>
> >> On Wed, Jul 21, 2010 at 5:02 AM, Georgi Guninski <guninski at guninski.com
> >
> >> wrote:
> >> > 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/
> >
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

The algorithm is correct, a proof: let n>1 an odd integer (for n=1 the
algorithm is correct).
before te while loop we know that n+1=2^l1*m1, but if the order is ord, then
2^ord==1 mod n (and this is the smallest positive integer), so
2^ord>=n-1=2^l1*m1-2, so 2^ord>=2^l1*m1-2 from this ord>=l1 (use that ord>1
and m1>=1). So we know that ord>=l1=res.

Let c=ord-res, we want to get a lower bound again for c. Observe that
2^ord==2^(l1+c)==1 mod n. (In the algorithm m1,m2,.. are odd integers less
than n, and l1,l2,..>=1, it is easy to see this.)

Use n+1=2^l1*m1:
2^(l1+c)==1==2^l1*m1 mod n, but n is odd, divide the equation by 2^l1:
2^c==m1 mod n, it is also true that:
2^c==m1==n+m1 mod n, but n+m1=2^l2*m2, so
2^c==2^l2*m2 mod n. If m1>1 then it is impossible that 2^c<n, otherwise
2^c=m1>1 but m1 is odd. So 2^c>=n and n<=2^l2*m2=n+m1<2*n from this we can
get also that c>=l2. So ord>=l1+l2. The other case is that m1=1 but the
solution of that c=0.

Next we get a lower bound for ord-l1-l2 and so on, while we reach m=1.