Multiplicative order: Difference between revisions

=={{header|Phix}}==

{{trans|Ruby}}

Note this is considerably slower than Ruby, which completes in a fraction of a second, mainly I suspect

due to the fact that bigatom.e operates on a digit-by-digit basis.

Also, ba_mod_exp is fairly likely to get added to bigatom.e in a future release, likewise

the other ba_xxx routines below have been earmarked for possible inclusion.

<lang Phix>include bigatom.e

function ba_mod_exp(object base, exponent, modulus)

-- base/exponent/modulus can be integer/string/bigatom

-- returns mod(power(base,exponent),modulus) [aka b^e%m], but in bigatoms and faster.

bigatom res = BA_ONE

base = ba_mod(base,modulus)

while ba_compare(exponent,0)!=0 do

if ba_mod(exponent,2)=BA_ONE then

res = ba_mod(ba_multiply(res,base),modulus)

end if

base = ba_mod(ba_multiply(base,base),modulus)

exponent = ba_idivide(exponent,2)

end while

return res

end function

function ba_factor(object n)

-- eg ba_factor(1000) -> {{2,3},{5,3}}, ie power(2,3)*power(5,3) == 8*125 == 1000.

-- (note that each res[i] is {bigatom,integer})

if ba_compare(n,BA_ZERO)=0 then return {} end if

sequence pf = {}

integer e = 0

while ba_mod(n,2)=BA_ZERO do

n = ba_idivide(n,2)

e += 1

end while

if e>0 then

pf = {{2,e}}

end if

bigatom s = ba_sqrt(n),

d = ba_new(3)

while ba_compare(n,BA_ONE)>0 do

if ba_compare(d,s)>0 then

d = ba_new(n)

end if

e = 0

while true do

bigatom r = ba_mod(n,d)

if r!=BA_ZERO then exit end if

n = ba_idivide(n,d)

e += 1

end while

if e>0 then

pf = append(pf,{d,e})

s = ba_sqrt(n)

end if

d = ba_add(d,2)

end while

return pf

end function

function ba_gcd(object m, n)

while ba_compare(n,BA_ZERO)!=0 do

{m,n} = {n,ba_mod(m,n)}

end while

return m

end function

function ba_lcm(object m, n)

return ba_mul(ba_idivide(m,ba_gcd(m,n)),n)

end function

function multi_order(object a, sequence p_and_k)

{object p, integer k} = p_and_k

bigatom pk = ba_power(p,k),

t = ba_mul(ba_sub(p,1),ba_power(p,ba_sub(k,1))),

r = BA_ONE

sequence pf = ba_factor(t)

for i=1 to length(pf) do

{object q, integer e} = pf[i]

bigatom x = ba_mod_exp(a,ba_idiv(t,ba_power(q,e)),pk)

--

-- previous attempts at this task resulted in an infinite loop,

-- so I added a quard; feel free to increase limit as needed.

--

integer guard = 0

while x!=BA_ONE do

r = ba_mul(r,q)

x = ba_mod_exp(x,q,pk)

guard += 1

if guard>100 then ?9/0 end if

end while

end for

return r

end function

function multiplicative_order(object a, m)

if ba_gcd(a,m)!=BA_ONE then return "(a,m) not coprime" end if

sequence pf = ba_factor(m)

bigatom res = BA_ONE

for i=1 to length(pf) do

res = ba_lcm(res,multi_order(a,pf[i]))

end for

return res

end function

constant b100 = ba_power(2,100)

function shorta(object n)

return iff(ba_compare(n,b100)>0?"[big]":ba_sprint(n))

end function

procedure mo_test(object a, n)

string res = ba_sprint(multiplicative_order(a, n))

printf(1,"ord(%s) mod %s = %s\n",{shorta(a),shorta(n),res})

end procedure

atom t = time()

mo_test(37, 1000)

mo_test(37, 3343)

mo_test(ba_add(ba_power(10,100),1), 7919)

mo_test(ba_add(ba_power(10,1000),1), 15485863)

mo_test(ba_sub(ba_power(10,10000),1), 22801763489)

mo_test(1511678068, 7379191741)

mo_test(3047753288, 2257683301)

?"==="

bigatom b = ba_sub(ba_power(10,20),1)

mo_test(2, b)

mo_test(17,b)

mo_test(54,100001)

--/*

-- this all works fine, but doubles the runtime...

bigatom b9090 = multiplicative_order(54,100001)

ba_printf(1,"%B\n",b9090)

if ba_compare(b9090,9090)!=0 then ?9/0 end if

ba_printf(1,"%B\n",ba_mod_exp(54,b9090,100001))

bool error = false

atom t1 = time()+1

for r=1 to 9090-1 do

if ba_compare(ba_mod_exp(54,r,100001),1)=0 then

printf(1,"ba_mod_exp(54,%d,100001) gives 1!\n",r)

error = true

exit

end if

if time()>t1 then

printf(1,"checking %d...\r",r)

t1 = time()+1

end if

end for

if not error then puts(1,"Everything checks.\n") end if

--*/

?elapsed(time()-t)</lang>

{{out}}

<pre>

ord(37) mod 1000 = 100

ord(37) mod 3343 = 1114

ord([big]) mod 7919 = 3959

ord([big]) mod 15485863 = 15485862

ord([big]) mod 22801763489 = 22801763488

ord(1511678068) mod 7379191741 = 614932645

ord(3047753288) mod 2257683301 = 62713425

"==="

ord(2) mod 99999999999999999999 = 3748806900

ord(17) mod 99999999999999999999 = 1499522760

ord(54) mod 100001 = 9090

"1 minute and 11s"

</pre>