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

[Vladimir Shevelev]

Very thanks for a proof. Your idea is very natural!

Best regards,
Vladimir

----- Original Message -----
From: Robert Gerbicz <robert.gerbicz at gmail.com>
Date: Wednesday, July 21, 2010 19:55
Subject: [seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> 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, 
> otherwise2^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.
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎