Rosetta Code

Multiplicative order: Difference between revisions

Page Discussion

Multiplicative order (view source)

Revision as of 05:07, 18 June 2019

1,146 bytes removed ,  4 years ago
→‎{{header|Phix}}: replaced with gmp version
m (→‎{{header|Sidef}}: added example for the built-in method)
(→‎{{header|Phix}}: replaced with gmp version)
Line 1,532:
=={{header|Phix}}==
{{trans|Ruby}}
{{libheader|mpfr}}
Note this is considerably slower than Ruby, which completes in a fraction of a second, mainly I suspect
<lang Phix>include mpfr.e
due to the fact that bigatom.e operates on a digit-by-digit basis.
 
procedure multi_order(mpz res, a, sequence p_and_k)
Also, ba_mod_exp is fairly likely to get added to bigatom.e in a future release, likewise
mpz pk = mpz_init(),
the other ba_xxx routines below have been earmarked for possible inclusion.
t = mpz_init(),
<lang Phix>include bigatom.e
x = mpz_init(),
 
q = mpz_init()
function ba_mod_exp(object base, exponent, modulus)
mpz_set_si(res,1)
-- base/exponent/modulus can be integer/string/bigatom
if length(p_and_k)=1 then
-- returns mod(power(base,exponent),modulus) [aka b^e%m], but in bigatoms and faster.
bigatom res string {ps} = BA_ONEp_and_k
base = ba_mod mpz_set_str(basepk,modulusps)
mpz_sub_ui(t,pk,1)
while ba_compare(exponent,0)!=0 do
else
if ba_mod(exponent,2)=BA_ONE then
atom {p, resk} = ba_mod(ba_multiply(res,base),modulus)p_and_k
end ifmpz_ui_pow_ui(pk,p,k)
base = ba_modmpz_ui_pow_ui(ba_multiply(baset,base)p,modulusk-1)
exponent = ba_idividempz_mul_si(exponentt,2t,p-1)
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
bigatomsequence spf = ba_sqrtmpz_prime_factors(nt),
for i=1 to d = ba_newlength(3pf) do
while ba_compare if length(n,BA_ONEpf[i])>0=1 dothen
string {fs} = pf[i]
if ba_compare(d,s)>0 then
d = ba_newmpz_set_str(nq,fs)
mpz_set(x,q)
else
{integer qi, integer ei} = pf[i]
mpz_set_si(q,qi)
mpz_pow_ui(x,q,ei)
end if
empz_fdiv_q(x, =t, 0x)
while true dompz_powm(x,a,x,pk)
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 guard; feel free to increase limit as needed.
--
integer guard = 0
while mpz_cmp_si(x,1)!=BA_ONE0 do
r = ba_mulmpz_mul(rres,res,q)
x = ba_mod_expmpz_powm(x,x,q,pk)
guard += 1
if guard>100 then ?9/0 end if -- (increase if rqd)
end while
end for
x = mpz_clear(x)
return r
end functionprocedure
function multiplicative_order(objectmpz a, m)
mpz res = mpz_init(1),
if ba_gcd(a,m)!=BA_ONE then return "(a,m) not coprime" end if
sequence pf ri = ba_factormpz_init(m)
mpz_gcd(ri,a,m)
bigatom res = BA_ONE
if mpz_cmp_si(ri,1)!=0 then return "(a,m) not coprime" end if
sequence pf = mpz_prime_factors(m,10000) -- (increase if rqd)
for i=1 to length(pf) do
res = ba_lcmmulti_order(resri,multi_order(a,pf[i]))
mpz_lcm(res,res,ri)
end for
return mpz_get_str(res )
end function
 
function shorta(mpz n)
constant b100 = ba_power(2,100)
string res = mpz_get_str(n)
 
integer lr = length(res)
function shorta(object n)
if lr>80 then
return iff(ba_compare(n,b100)>0?"[big]":ba_sprint(n))
res[6..-6] = "..."
res &= sprintf(" (%d digits)",lr)
end if
return res
end function
 
procedure mo_test(objectmpz 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
function i(atom i) return mpz_init(i) end function -- (ugh)
function p10(integer e,i) -- init to 10^e+i
mpz res = mpz_init()
mpz_ui_pow_ui(res,10,e)
mpz_add_si(res,res,i)
return res
end function
 
atom t = time()
mo_test(37i(3), 1000i(10))
mo_test(i(37), 3343i(1000))
mo_test(ba_addi(ba_power(10,10037),1 i(10000), 7919)
mo_test(ba_addi(ba_power(10,100037),1 i(3343), 15485863)
mo_test(ba_subi(ba_power(10,1000037),1 i(3344), 22801763489)
mo_test(1511678068i(2), 7379191741i(1000))
mo_test(3047753288p10(100,+1), 2257683301i(7919))
mo_test(p10(1000,+1), i(15485863))
mo_test(p10(10000,-1), i(22801763489))
mo_test(i(1511678068), i(7379191741))
mo_test(i(3047753288), i(2257683301))
?"==="
bigatommpz b = ba_subp10(ba_power(10,20),-1)
mo_test(i(2), b)
mo_test(i(17),b)
mo_test(i(54),i(100001))
string s9090 = multiplicative_order(mpz_init(54),mpz_init(100001))
--/* -- this all works fine, but doubles the runtime...
if s9090!="9090" then ?9/0 end if
bigatom b9090 = multiplicative_order(54,100001)
mpz m54 = mpz_init(54),
ba_printf(1,"%B\n",b9090)
m100001 = mpz_init(100001)
if ba_compare(b9090,9090)!=0 then ?9/0 end if
mpz_powm_ui(b,m54,9090,m100001)
ba_printf(1,"%B\n",ba_mod_exp(54,b9090,100001))
printf(1,"%s\n",mpz_get_str(b))
bool error = false
atom t1 = time()+1
for r=1 to 9090-1 do
mpz_powm_ui(b,m54,r,m100001)
if ba_compare(ba_mod_exp(54,r,100001),1)=0 then
if mpz_cmp_si(b,1)=0 then
printf(1,"ba_mod_exp(54,%d,100001) gives 1!\n",r)
printf(1,"mpz_powm_ui(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
printf(1,"Everything checks. (%s)\n",{elapsed(time()-t)})
--*/
?elapsed(time()-t)end if</lang>
{{out}}
<pre>
ord(3) mod 10 = 4
ord(37) mod 1000 = 100
ord(37) mod 10000 = 500
ord(37) mod 3343 = 1114
ord([big]37) mod 79193344 = 395920
ord([big]2) mod 154858631000 = 15485862(a,m) not coprime
ord([big]10000...00001 (101 digits)) mod 228017634897919 = 228017634883959
ord(10000...00001 (1001 digits)) mod 15485863 = 15485862
ord(99999...99999 (10000 digits)) mod 22801763489 = 22801763488
ord(1511678068) mod 7379191741 = 614932645
ord(3047753288) mod 2257683301 = 62713425
Line 1,692 ⟶ 1,663:
ord(17) mod 99999999999999999999 = 1499522760
ord(54) mod 100001 = 9090
1
"1 minute and 11s"
Everything checks. (0.2s)
</pre>
 
Petelomax
7,818

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/48330"