Multiplicative order: Difference between revisions

Line 1,588:

<lang Phix>~~include mpfr.e~~

without javascript_semantics

requires(64)

procedure multi_order(mpz res, a, sequence p_and_k)

include mpfr.e

mpz pk = mpz_init(),

t = mpz_init(),

procedure multi_order(mpz res, a, sequence p_and_k)

x = mpz_init(),

mpz pk = mpz_init(),

q = mpz_init()

t = mpz_init(),

mpz_set_si(res,1)

x = mpz_init(),

if length(p_and_k)=1 then

q = mpz_init()

string {ps} = p_and_k

mpz_set_si(res,1)

mpz_set_str(pk,ps)

if length(p_and_k)=1 then

mpz_sub_ui(t,pk,1)

string {ps} = p_and_k

else

mpz_set_str(pk,ps)

atom {p, k} = p_and_k

mpz_sub_ui(t,pk,1)

mpz_ui_pow_ui(pk,p,k)

else

mpz_ui_pow_ui(t,p,k-1)

integer {p, k} = p_and_k -- (typecheck on 32-bit)

mpz_mul_si(t,t,p-1)

mpz_ui_pow_ui(pk,p,k)

end if

mpz_ui_pow_ui(t,p,k-1)

sequence pf = mpz_prime_factors(t)

mpz_mul_si(t,t,p-1)

for i=1 to length(pf) do

end if

if length(pf[i])=1 then

sequence pf = mpz_prime_factors(t)

string {fs} = pf[i]

for i=1 to length(pf) do

mpz_set_str(q,fs)

if length(pf[i])=1 then

mpz_set(x,q)

string {fs} = pf[i]

else

mpz_set_str(q,fs)

{integer qi, integer ei} = pf[i]

mpz_set(x,q)

mpz_set_si(q,qi)

~~mpz_pow_ui(x,q,ei)~~

else

{integer qi, integer ei} = pf[i]

end if

mpz_set_si(q,qi)

mpz_fdiv_q(x, t, x)

mpz_pow_ui(x,q,ei)

mpz_powm(x,a,x,pk)

end if

integer guard = 0

mpz_fdiv_q(x, t, x)

while mpz_cmp_si(x,1)!=0 do

mpz_powm(x,a,x,pk)

mpz_mul(res,res,q)

integer guard = 0

mpz_powm(x,x,q,pk)

while mpz_cmp_si(x,1)!=0 do

guard += 1

mpz_mul(res,res,q)

if guard>100 then ?9/0 end if -- (increase if rqd)

mpz_powm(x,x,q,pk)

end while

guard += 1

end for

if guard>100 then ?9/0 end if -- (increase if rqd)

x = mpz_free(x)

end while

end procedure

end for

x = mpz_free(x)

function multiplicative_order(mpz a, m)

end procedure

mpz res = mpz_init(1),

ri = mpz_init()

function multiplicative_order(mpz a, m)

mpz_gcd(ri,a,m)

mpz res = mpz_init(1),

if mpz_cmp_si(ri,1)!=0 then return "(a,m) not coprime" end if

ri = mpz_init()

sequence pf = mpz_prime_factors(m,10000) -- (increase if rqd)

mpz_gcd(ri,a,m)

for i=1 to length(pf) do

if mpz_cmp_si(ri,1)!=0 then return "(a,m) not coprime" end if

multi_order(ri,a,pf[i])

sequence pf = mpz_prime_factors(m,10000) -- (increase if rqd)

mpz_lcm(res,res,ri)

for i=1 to length(pf) do

end for

multi_order(ri,a,pf[i])

return mpz_get_str(res)

mpz_lcm(res,res,ri)

end function

end for

return mpz_get_str(res)

function shorta(mpz n)

end function

string res = mpz_get_str(n)

integer lr = length(res)

function shorta(mpz n)

if lr>80 then

string res = mpz_get_str(n)

res[6..-6] = "..."

integer lr = length(res)

res &= sprintf(" (%d digits)",lr)

if lr>80 then

end if

res[6..-6] = "..."

return res

res &= sprintf(" (%d digits)",lr)

end function

end if

return res

procedure mo_test(mpz a, n)

end function

string res = multiplicative_order(a, n)

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

procedure mo_test(mpz a, n)

end procedure

string res = multiplicative_order(a, n)

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

function i(atom i) return mpz_init(i) end function -- (ugh)

end procedure

function p10(integer e,i) -- init to 10^e+i

mpz res = mpz_init()

function i(atom i) return mpz_init(i) end function -- (ugh)

mpz_ui_pow_ui(res,10,e)

function p10(integer e,i) -- init to 10^e+i

mpz_add_si(res,res,i)

mpz res = mpz_init()

return res

mpz_ui_pow_ui(res,10,e)

end function

mpz_add_si(res,res,i)

return res

atom t = time()

end function

mo_test(i(3), i(10))

mo_test(i(37), i(1000))

atom t = time()

mo_test(i(37), i(10000))

mo_test(i(3), i(10))

mo_test(i(37), i(3343))

mo_test(i(37), i(1000))

mo_test(i(37), i(3344))

mo_test(i(37), i(10000))

mo_test(i(2), i(1000))

mo_test(i(37), i(3343))

mo_test(p10(100,+1), i(7919))

mo_test(i(37), i(3344))

mo_test(p10(1000,+1), i(15485863))

mo_test(i(2), i(1000))

mo_test(p10(10000,-1), i(22801763489))

mo_test(p10(100,+1), i(7919))

mo_test(i(1511678068), i(7379191741))

mo_test(p10(1000,+1), i(15485863))

mo_test(i(3047753288), i(2257683301))

mo_test(p10(10000,-1), i(22801763489))

?"==="

mo_test(i(1511678068), i(7379191741))

mpz b = p10(20,-1)

mo_test(i(3047753288), i(2257683301))

mo_test(i(2), b)

?"==="

mo_test(i(17),b)

mpz b = p10(20,-1)

mo_test(i(54),i(100001))

mo_test(i(2), b)

string s9090 = multiplicative_order(mpz_init(54),mpz_init(100001))

mo_test(i(17),b)

if s9090!="9090" then ?9/0 end if

mo_test(i(54),i(100001))

mpz m54 = mpz_init(54),

string s9090 = multiplicative_order(mpz_init(54),mpz_init(100001))

m100001 = mpz_init(100001)

if s9090!="9090" then ?9/0 end if

mpz_powm_ui(b,m54,9090,m100001)

mpz m54 = mpz_init(54),

printf(1,"%s\n",mpz_get_str(b))

m100001 = mpz_init(100001)

bool error = false

mpz_powm_ui(b,m54,9090,m100001)

for r=1 to 9090-1 do

printf(1,"%s\n",mpz_get_str(b))

mpz_powm_ui(b,m54,r,m100001)

bool error = false

if mpz_cmp_si(b,1)=0 then

for r=1 to 9090-1 do

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

mpz_powm_ui(b,m54,r,m100001)

error = true

if mpz_cmp_si(b,1)=0 then

exit

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

end if

error = true

end for

exit

if not error then

end if

printf(1,"Everything checks. (%s)\n",{elapsed(time()-t)})

end for

end if</lang>

if not error then

printf(1,"Everything checks. (%s)\n",{elapsed(time()-t)})

end if

<pre>