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

[Alexander P-sky]

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/
>