verzija: SageMath 8.4
%display ascii_art
[NN,ZZ,QQ,RR,CC]
[24 in NN, 24 in ZZ, -32 in NN, -32 in ZZ]
[2/3 in ZZ, 2/3 in QQ, 2.3 in QQ, 2.3 in RR, sqrt(2) in QQ, sqrt(2) in RR]
[sqrt(-2) in RR, sqrt(-2) in CC, I in CC]
type(NN)
type(CC)
floor(5.23)
ceil(5.23)
floor(pi)
ceil(pi)
floor(-5.23)
ceil(-5.23)
plot(floor(x),(x,-3,3),thickness=3,figsize=[4,4])
plot(floor(x),(x,-3,3),thickness=3,exclude=[-3..3],figsize=[4,4])
plot(ceil(x),(x,-3,3),thickness=3,figsize=[4,4])
plot(ceil(x),(x,-3,3),thickness=3,exclude=[-3..3],figsize=[4,4])
slika1=plot(floor(x),(x,-3,3),color="blue",thickness=3,exclude=[-3..3])
slika2=plot(ceil(x),(x,-3,3),color="red",thickness=3,exclude=[-3..3])
show(slika1+slika2,figsize=[4,4])
500//17
500%17
-500//17
-500%17
Neočekivani rezultati
500//-17
500%-17
Definiramo svoje funkcije koje će raditi prema našim definicijama
def kvocijent(a,b):
if b==0:
return "Error: dijeljenje s nulom"
elif b>0:
return floor(a/b)
else:
return ceil(a/b)
def ostatak(a,b):
if b==0:
return "Error: dijeljenje s nulom"
elif b>0:
return a-floor(a/b)*b
else:
return a-ceil(a/b)*b
kvocijent(500,17)
ostatak(500,17)
kvocijent(500,-17)
ostatak(500,-17)
ostatak(-50,0)
gcd(30,18)
gcd(-30,18)
gcd(-15,-17)
gcd(252,200)
gcd([15,30,48])
Jedno cjelobrojno rješenje jednadžbe 252x+200y=M(252,200)
xgcd(252,200)
lcm(8,12)
lcm(-8,12)
lcm([12,5,14])
lcm(252,200)
is_prime(1023)
is_prime(17)
map(lambda x: is_prime(x),[1023,17])
is_prime_power(64)
is_prime_power(111934216)
%display latex
factor(40)
factor(4063)
factor(10468)
factor(10^30+1)
%display ascii_art
divisors(40)
divisors(4063)
divisors(10468)
[faktor for faktor in divisors(40) if is_prime(faktor)]
[faktor for faktor in divisors(4063) if is_prime(faktor)]
[faktor for faktor in divisors(10468) if is_prime(faktor)]
[faktor for faktor in divisors(10^30+1) if is_prime(faktor)]
Primes()
23 in Primes()
1 in Primes()
primes_first_n(30)
list_plot(primes_first_n(30),figsize=[5,5])
list_plot(primes_first_n(30),plotjoined=True,figsize=[5,5])
list_plot(primes_first_n(100),color="red",figsize=[5,5])
list_plot(primes_first_n(100),plotjoined=True,color="red",figsize=[5,5])
primes_first_n(10)[-1]
prime_range(41,200)
prime_powers(41,150)
next_prime(100)
next_prime(31)
next_prime(44)
next_prime(2^100)
previous_prime(100)
previous_prime(31)
previous_prime(44)
previous_prime(2^100)
prime_pi(100)
prime_pi(10000)
prime_pi(34.56)
prime_pi(pi^100)
floor(pi^100).ndigits(10)
n(pi^100)
prime_pi(pi^20)
[prime_pi(n) for n in xrange(1,50)]
[(n,prime_pi(n)) for n in xrange(1,50)]
Teorem o prostim brojevima
prvi=list_plot([prime_pi(n) for n in xrange(1,101)])
show(prvi,figsize=[7,5])
drugi=plot(x/log(x),(x,1,100),color="red")
show(drugi,figsize=[7,5])
show(prvi+drugi,figsize=[7,5])
def teorem_prosti_brojevi(n,xy=[7,5]):
slika1=list_plot([prime_pi(k) for k in xrange(1,n)])
slika2=plot(x/log(x),(x,1,n),color="red")
slika3=show(slika1+slika2,figsize=xy)
return slika3
teorem_prosti_brojevi(100)
teorem_prosti_brojevi(1000)
teorem_prosti_brojevi(10000)
teorem_prosti_brojevi(100000)
[2e4,8e4,1e5]
slučajni prosti broj manji od 200
random_prime(200)
random_prime(200)
lista od 10 slučajnih prostih brojeva manjih od 200
[random_prime(200) for n in xrange(10)]
slučajni prosti broj između 200 i 500
random_prime(500,lbound=200)
slučajni prosti broj sa 12 znamenaka
random_prime(10^12,lbound=10^11)
3x4 matrica slučajnih prostih brojeva manjih od 1000
[[random_prime(1000) for n in xrange(3)] for m in xrange(4)]
matrix([[random_prime(1000) for n in xrange(3)] for m in xrange(4)])
dva slučajna prosta broja za RSA kriptosustav
(p,q)=(random_prime(2^640,lbound=2^639),random_prime(2^640,lbound=2^639))
p
q
brojevi p i q u bazi 10 imaju 193 znamenke, a u bazi 2 imaju 640 znamenaka (bitova)
p.ndigits(10)
p.ndigits(2)
[q.ndigits(10),q.ndigits(2)]
lista znamenaka broja p u bazi 2 (pazite, znamenke su navedene u obrnutom redoslijedu)
p.digits(2)
broj=4
(broj.digits(2),list(reversed(broj.digits(2))))
opcija "proof=False" daje pseudoprosti broj
time random_prime(2^640,lbound=2^639)
time random_prime(2^640,lbound=2^639,proof=False)
time random_prime(2^640,lbound=2^639,proof=True)
$15x\equiv 1\!\pmod{341}$ rješenje: $x=91$
inverse_mod(15,341)
$10x\equiv 1\!\pmod{12}$ nema rješenja
inverse_mod(10,12)
def lin_kong(a,b,n):
d=gcd(a,n)
if b%d!=0:
return False
a1=a//d
b1=b//d
n1=n//d
x=(inverse_mod(a1,n1)*b1)%n1
rjesenja=[x+k*n1 for k in xrange(d)]
return rjesenja
$79x\equiv 15\!\pmod{722}$ rješenje: $119$
lin_kong(79,15,722)
$155x\equiv 1185\!\pmod{1405}$ rješenja: $198, 479, 760, 1041, 1322$
lin_kong(155,1185,1405)
$15x\equiv 1\!\pmod{341}$ rješenje: $91$
lin_kong(15,1,341)
$10x\equiv 1\!\pmod{12}$ nema rješenja
lin_kong(10,1,12)
$65x\equiv 27\!\pmod{169}$ nema rješenja
lin_kong(65,27,169)
def lin_kong_rucno(a,b,n):
qi=[]
yi=[0,1]
n1,q,r1,d=a,n//a,n%a,a
while r1!=0:
qi.append(q)
yi.append(yi[-2]-q*yi[-1])
q=n1//r1
n1,r1=r1,n1%r1
if r1!=0: d=r1
if b%d!=0: return False
a1,b1,n1=a//d,b//d,n//d
x1=(yi[-1]*b1)%n1
rjesenja=[x1+k*n1 for k in xrange(d)]
tablica=table([["$i$"]+range(-1,len(yi)-1)+["rjesenja"],["$q_i$"," "," "]+qi+[rjesenja],["$y_i$"]+yi+
["$(a_1,b_1,n_1)=(%d,%d,%d)$"%(a1,b1,n1)]])
return tablica
lin_kong_rucno(79,15,722)
lin_kong_rucno(155,1185,1405)
lin_kong_rucno(10,1,12)
crt([1,8,10],[4,9,25])
crt([4,1,7],[5,12,14])
crt([2,1,7],[3,12,14])
Funkcija koja daje rješenje sustava kongruencija pomoću kineskog teorema o ostacima na način kojeg provodimo ručnim rješavanjem. Na izlazu se vraća rječnik u kojemu su dane vrijednosti za $n, k_i, x_i, x_0, x_{0,mod}$.
def KTO_rucno(A,N):
"""Daje rjesenje sustava kongruencija x=a_i(mod n_i) pomocu kineskog teorema o ostacima
na nacin kojeg provodimo rucnim rjesavanjem.
Moduli n_i moraju biti u parovima relativno prosti. Na izlazu se vraca rjecnik u kojemu su
dane vrijednosti za n, k_i, x_i, x_0 i x0_mod.
A je lista a_i-ova, a N je lista n_i-ova."""
for t in Combinations(N,2).list():
if gcd(t[0],t[1])!=1:
return "Error: moduli nisu u parovima relativno prosti."
n=prod(N)
ki=map(lambda x: n/x,N)
xi=[]
for i in xrange(len(N)):
xi.append(int(solve_mod([ki[i]*x==A[i]],N[i])[0][0]))
x0=sum(map(lambda x: x[0]*x[1],zip(ki,xi)))
x0mod=x0%n
izlaz=dict(zip(['n','k_i','x_i','x0','x0_mod'],[n,ki,xi,x0,x0mod]))
return izlaz
KTO_rucno([1,8,10],[4,9,25])
KTO_rucno([4,1,7],[5,12,14])
euler_phi(17)
euler_phi(28)
[euler_phi(n) for n in xrange(1,51)]
list_plot([euler_phi(n) for n in xrange(1,51)],xmax=55,figsize=[5,4])
filter(lambda n: gcd(100,n)==1,range(100))
def reducirani_sustav_ostataka(m):
ostaci=filter(lambda n: gcd(m,n)==1,range(m))
return ostaci
reducirani_sustav_ostataka(100)
reducirani_sustav_ostataka(1000)
3^502*7^201%100
time 45^33333333%342
time power_mod(45,33333333,342)
var('x,y')
solve_mod([x+5*y==3,4*x+5*y==1],8)
solve_mod([3*x+5*y==14,5*x+9*y==6],28)
solve_mod([2*x+3*y==6,3*x+y==2],7)
solve_mod([2*x+3*y==6,3*x+y==2],5*6*7*11)
solve_mod([3*x+5*y==14,5*x+9*y==6],100)
solve_mod([79*x==15],722)
Mod(2,7).multiplicative_order()
type(Mod(2,7))
type(mod(2,7))
Mod(16,29).multiplicative_order()
Mod(12,28).multiplicative_order()
Mod(2,7) in IntegerModRing(7)
mod(2,7) in IntegerModRing(7)
primitive_root(7)
filter(lambda x: Mod(x,7).multiplicative_order()==euler_phi(7), range(1,7))
filter(lambda x: Mod(x,41).multiplicative_order()==euler_phi(41), range(1,41))
filter(lambda x: gcd(x,12)==1 and Mod(x,12).multiplicative_order()==euler_phi(12), range(1,12))
primitive_root(12)
$n=41$
reducirani_sustav_ostataka(41)
[mod(6^k,41) for k in xrange(euler_phi(41))]
sorted([mod(6^k,41) for k in xrange(euler_phi(41))])
$n=50$
primitive_root(50)
reducirani_sustav_ostataka(50)
sorted([mod(27^k,50) for k in xrange(euler_phi(50))])
solve_mod([x^5==2],7)
solve_mod([x^12==37],41)
filter(lambda x: mod(7^x,17)==6, range(17))
filter(lambda x: mod(3^x,23)==2, range(23))
solve_mod([2*x^8==5],13)
solve_mod([x^5==2],12)
solve_mod([x^5==4],12)
filter(lambda x: mod(x^5,12)==4, range(12))
time solve_mod([x^7==17],322122548)
%display latex
factor(322122548)
Ovdje želimo naglasiti razliku između naredbi mod (ili Mod) i naredbe % (za dobivanje ostatka pri dijeljenju dva cijela broja). Na prvi pogled se čini da te naredbe rade istu stvar, ali nije baš tako. Doduše, na izlazu daju kao isti rezultate, ali te rezultate SAGE potpuno drukčije doživljava. Pogledajmo na jednom primjeru tu razliku.
%display ascii_art
37%14
type(37%14)
Kako na 37%14 SAGE gleda kao na element iz prstena $\mathbb{Z}$, zbrajanje i množenje se odvija u prstenu $\mathbb{Z}$ i dobivamo očekivani rezultat.
37%14+5*14
Da li je tako i s naredbom mod?
mod(37,14)
type(mod(37,14))
Kako na mod(37,14) SAGE gleda kao na element iz prstena $\mathbb{Z}_{14}$, tada se zbrajanje i množenje odvijaju u prstenu $\mathbb{Z}_{14}$. Stoga rezultat kojeg je vratio SAGE nije bug, već je to stvarno dobar rezultat. Naime, u prstenu $\mathbb{Z}_{14}$ svi višekratnici broja 14 su zapravo jednaki 0, pa je tako i $5\cdot14$ također jednako 0 jer se operacije zbrajanja i množenja u prstenu $\mathbb{Z}_{14}$ rade modulo 14.
mod(37,14)+5*14