Teorija brojeva u pythonu
In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
In [3]:
platform.python_version()
Out[3]:
In [4]:
import sympy as sm
In [5]:
sm.__version__
Out[5]:
In [6]:
import numpy as np
In [7]:
np.__version__
Out[7]:
In [8]:
import itertools as it
In [9]:
import random as ran
In [10]:
from pylab import *
In [11]:
%matplotlib inline
In [12]:
import matplotlib
In [13]:
matplotlib.__version__
Out[13]:
In [14]:
import DSTG
Cjelobrojne funkcije
In [15]:
np.floor(5.23)
Out[15]:
In [16]:
sm.floor(5.23)
Out[16]:
In [17]:
np.ceil(5.23)
Out[17]:
In [18]:
sm.ceiling(5.23)
Out[18]:
In [19]:
np.floor(np.pi)
Out[19]:
In [20]:
sm.floor(sm.pi)
Out[20]:
In [21]:
np.ceil(np.pi)
Out[21]:
In [22]:
sm.ceiling(sm.pi)
Out[22]:
In [23]:
np.floor(-5.23)
Out[23]:
In [24]:
sm.floor(-5.23)
Out[24]:
In [25]:
np.ceil(-5.23)
Out[25]:
In [26]:
sm.ceiling(-5.23)
Out[26]:
Graf cjelobrojne funkcije $f(x)=\lfloor x\rfloor$
In [27]:
t = np.arange(-3.0, 3.0, 0.01)
grid(True)
plot(t,np.floor(t),linewidth=3.0,color='b')
ylim([-3,3]);
In [28]:
grid(True)
for i in range(-3,3):
t=np.arange(i,i+1,0.01)
plot(t,np.floor(t),linewidth=3.0,color='b')
ylim([-3,3]);
Graf cjelobrojne funkcije $f(x)=\lceil x\rceil$
In [29]:
t = np.arange(-3.0, 3.0, 0.01)
grid(True)
plot(t,np.ceil(t),linewidth=3.0,color='r')
ylim([-3,3]);
In [30]:
grid(True)
for i in range(-3,3):
t=np.arange(i+0.01,i+1,0.01)
plot(t,np.ceil(t),linewidth=3.0,color='r')
ylim([-3,3]);
Cjelobrojne funkcije $\lfloor x\rfloor$ i $\lceil x\rceil$ na istoj slici
In [31]:
grid(True)
for i in range(-3,3):
t1=np.arange(i,i+1,0.01)
t2=np.arange(i+0.01,i+1,0.01)
plot(t1,np.floor(t1),linewidth=3.0,color='b')
plot(t2,np.ceil(t2),linewidth=3.0,color='r')
Teorem o dijeljenju s ostatkom
In [32]:
500//17
Out[32]:
In [33]:
500%17
Out[33]:
In [34]:
-500//17
Out[34]:
In [35]:
-500%17
Out[35]:
Neočekivani rezultati
In [36]:
500//-17
Out[36]:
In [37]:
500%-17
Out[37]:
Implementirane funkcije rade prema našim definicijama
In [38]:
DSTG.kvocijent(500,17)
Out[38]:
In [39]:
DSTG.ostatak(500,17)
Out[39]:
In [40]:
DSTG.kvocijent(500,-17)
Out[40]:
In [41]:
DSTG.ostatak(500,-17)
Out[41]:
In [42]:
DSTG.ostatak(-500,0)
Out[42]:
Najveća zajednička mjera
In [43]:
np.gcd(30,18)
Out[43]:
In [44]:
sm.gcd(30,18)
Out[44]:
In [45]:
np.gcd(-30,18)
Out[45]:
In [46]:
sm.gcd(-30,18)
Out[46]:
In [47]:
np.gcd(-15,-17)
Out[47]:
In [48]:
sm.gcd(-15,-17)
Out[48]:
In [49]:
np.gcd(252,200)
Out[49]:
In [50]:
sm.gcd(252,200)
Out[50]:
Jedno cjelobrojno rješenje jednadžbe $252x+200y=M(252,200)$
In [51]:
sm.gcdex(252,200)
Out[51]:
In [52]:
DSTG.euklid_rucno(252,200)
Out[52]:
Najmanji zajednički višekratnik
In [53]:
np.lcm(8,12)
Out[53]:
In [54]:
sm.lcm(8,12)
Out[54]:
In [55]:
np.lcm(252,200)
Out[55]:
In [56]:
sm.lcm(252,200)
Out[56]:
In [57]:
np.lcm(-8,12)
Out[57]:
In [58]:
sm.lcm(-8,12)
Out[58]:
In [59]:
np.lcm(np.lcm(12,5),14)
Out[59]:
In [60]:
sm.lcm_list([12,5,14])
Out[60]:
Prosti brojevi
Ispitivanje da li je broj prost
In [61]:
sm.isprime(1023)
Out[61]:
In [62]:
sm.isprime(17)
Out[62]:
In [63]:
list(map(lambda x: sm.isprime(x), [1023,17]))
Out[63]:
Ispitivanje prostosti velikih prirodnih brojeva pomoću Miller-Rabinovog testa
In [64]:
dat=open("P1.txt")
p1=int(dat.read())
dat.close()
dat=open("P2.txt")
p2=int(dat.read())
dat.close()
Broj $\ p_1$ je sigurno složeni broj.
In [65]:
DSTG.ispis(p1,80)
In [66]:
sm.isprime(p1)
Out[66]:
In [67]:
sm.ntheory.primetest.mr(p1,[ran.randint(1,p1) for k in range(20)])
Out[67]:
In [68]:
DSTG.ispis(p2,80)
Broj $\ p_2$ je vjerojatno prosti broj. Test se ponavlja po defaultu $20$ puta.
In [69]:
sm.isprime(p2)
Out[69]:
In [70]:
sm.ntheory.primetest.mr(p2,[ran.randint(1,p2) for k in range(20)])
Out[70]:
Broj $\ p_2$ je vjerojatno prosti broj s još većom vjerojatnošću. Ovaj put se test ponavlja $30$ puta.
In [71]:
sm.ntheory.primetest.mr(p2,[ran.randint(1,p2) for k in range(30)])
Out[71]:
Rastav broja na proste faktore
In [72]:
sm.ntheory.factorint(40)
Out[72]:
In [73]:
sm.ntheory.factorint(4063)
Out[73]:
In [74]:
sm.ntheory.factorint(10468)
Out[74]:
In [75]:
sm.ntheory.factorint(10**30+1)
Out[75]:
Djelitelji prirodnog broja
In [76]:
sm.ntheory.divisors(40)
Out[76]:
In [77]:
sm.ntheory.divisors(4063)
Out[77]:
In [78]:
sm.ntheory.divisors(10468)
Out[78]:
In [79]:
DSTG.ispis(sm.ntheory.divisors(10**30+1),80)
Prosti djelitelji prirodnog broja
In [80]:
sm.ntheory.primefactors(40)
Out[80]:
In [81]:
sm.ntheory.primefactors(4063)
Out[81]:
In [82]:
sm.ntheory.primefactors(10468)
Out[82]:
In [83]:
sm.ntheory.primefactors(10**30+1)
Out[83]:
Skup prostih brojeva
In [84]:
sm.sieve._list
Out[84]:
In [85]:
17 in sm.sieve
Out[85]:
In [86]:
25 in sm.sieve
Out[86]:
In [87]:
1047 in sm.sieve
Out[87]:
In [88]:
sm.isprime(17981)
Out[88]:
In [89]:
17981 in sm.sieve
Out[89]:
proširenje sita do svih prostih brojeva manjih ili jednakih od 20000
In [90]:
sm.sieve.extend(20000)
In [91]:
sm.sieve._list
Out[91]:
In [92]:
17981 in sm.sieve
Out[92]:
Prvih 30 prostih brojeva
In [93]:
DSTG.ispis([sm.ntheory.prime(n) for n in range(1,31)],80)
In [94]:
figure(figsize=(10,8))
grid(True)
t=[sm.ntheory.prime(n) for n in range(1,31)]
plot(range(1,31),t,'o',markersize=8,c='r')
xticks(np.arange(0,31,1))
yticks(np.arange(0,120,10))
xlim([0,31]);
In [95]:
figure(figsize=(10,8))
grid(True)
t=[sm.ntheory.prime(n) for n in range(1,31)]
plot(range(1,31),t,'-',linewidth=3,c='r')
xticks(np.arange(0,31,1))
yticks(np.arange(0,120,10))
xlim([0,31]);
Deseti po redu prosti broj
In [96]:
sm.ntheory.prime(10)
Out[96]:
Svi prosti brojevi između $41$ i $200$
In [97]:
DSTG.ispis(list(sm.ntheory.primerange(41,201)),80)
Svi brojevi između $41$ i $200$ koji su potencije prostog broja
In [98]:
DSTG.ispis(list(filter(lambda x: len(sm.ntheory.primefactors(x))==1,range(41,201))),80)
Najmanji prosti broj veći od $n$
In [99]:
sm.ntheory.nextprime(100)
Out[99]:
In [100]:
sm.ntheory.nextprime(31)
Out[100]:
In [101]:
sm.ntheory.nextprime(44)
Out[101]:
In [102]:
sm.ntheory.nextprime(2**100)
Out[102]:
Najveći prosti broj manji od $n$
In [103]:
sm.ntheory.prevprime(100)
Out[103]:
In [104]:
sm.ntheory.prevprime(31)
Out[104]:
In [105]:
sm.ntheory.prevprime(44)
Out[105]:
In [106]:
sm.ntheory.prevprime(2**100)
Out[106]:
Prosti brojevi manji od $1000$
In [107]:
DSTG.ispis(list(sm.ntheory.primerange(1,1000)),80)
Slučajni prosti broj s $n$ znamenaka
In [108]:
sm.ntheory.randprime(1,10**2)
Out[108]:
In [109]:
sm.ntheory.randprime(1,10**2)
Out[109]:
In [110]:
sm.ntheory.randprime(1,10**10)
Out[110]:
Slučajni prosti broj između 5002 i 23421
In [111]:
sm.ntheory.randprime(5002,23421)
Out[111]:
Dva slučajna prosta broja za RSA kriptosustav
In [112]:
p=sm.ntheory.randprime(1,10**200)
In [113]:
q=sm.ntheory.randprime(1,10**200)
In [114]:
DSTG.ispis(p,80)
In [115]:
DSTG.ispis(q,80)
In [116]:
DSTG.ispis(p*q,80)
In [117]:
p1=sm.ntheory.randprime(2**639,2**640)
In [118]:
q1=sm.ntheory.randprime(2**639,2**640)
In [119]:
DSTG.ispis(p1,80)
In [120]:
DSTG.ispis(q1,80)
In [121]:
DSTG.ispis(p1*q1,80)
Linearne kongruencije
$15x\equiv1\!\pmod{341}\qquad$ rješenje: $x=91$
In [122]:
DSTG.lin_kong_rucno(15,1,341,izlaz='rjecnik')
Out[122]:
In [123]:
DSTG.lin_kong_rucno(15,1,341)
Out[123]:
$10x\equiv1\!\pmod{12}\qquad$ nema rješenja
In [124]:
DSTG.lin_kong_rucno(10,1,12)
Out[124]:
$79x\equiv15\!\pmod{722}\qquad$ rješenje: $x=119$
In [125]:
DSTG.lin_kong_rucno(79,15,722,izlaz='rjecnik')
Out[125]:
In [126]:
DSTG.lin_kong_rucno(79,15,722)
Out[126]:
$155x\equiv1185\!\pmod{1405}\qquad$ rješenja: $x=198, 479, 760, 1041, 1322$
In [127]:
DSTG.lin_kong_rucno(155,1185,1405,izlaz='rjecnik')
Out[127]:
In [128]:
DSTG.lin_kong_rucno(155,1185,1405)
Out[128]:
Kineski teorem o ostacima
$x\equiv1\!\pmod{4},\quad x\equiv8\!\pmod{9},\quad x\equiv10\!\pmod{25}$
In [129]:
from sympy.ntheory.modular import crt
crt([4,9,25],[1,8,10])
Out[129]:
$x\equiv4\!\pmod{5},\quad x\equiv1\!\pmod{12},\quad x\equiv7\!\pmod{77}$
In [130]:
crt([5,12,77],[4,1,7])
Out[130]:
Funkcija koja ispisuje sve korake kod ručnog rješavanja sustava kongruencija pomoću kineskog teorema o ostacima
$x\equiv1\!\pmod{4},\quad x\equiv8\!\pmod{9},\quad x\equiv10\!\pmod{25}$
In [131]:
DSTG.KTO_rucno([1,8,10],[4,9,25],izlaz='rjecnik')
Out[131]:
In [132]:
DSTG.KTO_rucno([1,8,10],[4,9,25])
Out[132]:
$x\equiv4\!\pmod{5},\quad x\equiv1\!\pmod{12},\quad x\equiv7\!\pmod{14}$
In [133]:
DSTG.KTO_rucno([4,1,7],[5,12,14])
Out[133]:
In [134]:
from sympy.ntheory.modular import solve_congruence
solve_congruence((4,5),(1,12),(7,14))
Out[134]:
Eulerova funkcija
In [135]:
sm.ntheory.totient(17)
Out[135]:
In [136]:
sm.ntheory.totient(28)
Out[136]:
In [137]:
DSTG.ispis([sm.ntheory.totient(n) for n in range(1,51)],80)
In [138]:
figure(figsize=(12,8))
grid(True)
t=[sm.ntheory.totient(n) for n in range(1,51)]
plot(range(1,51),t,'o',markersize=8)
xticks(np.arange(0,51,2))
yticks(np.arange(0,50,5))
xlim([0,51]);
Kako dobiti listu svih prirodnih brojeva manjih od 100 koji su relativno prosti sa 100?
In [139]:
DSTG.ispis(list(filter(lambda n: np.gcd(100,n)==1,range(100))),80)
In [140]:
def reducirani_sustav_ostataka(m):
ostaci=list(filter(lambda n: np.gcd(m,n)==1,range(m)))
return ostaci
In [141]:
DSTG.ispis(reducirani_sustav_ostataka(100),80)
In [142]:
DSTG.ispis(reducirani_sustav_ostataka(1000),80)
Posljednje dvije znamenke broja $3^{502}\cdot7^{201}$ u njegovom dekadskom zapisu
In [143]:
(3**502*7**201)%100
Out[143]:
Za veće potencije je bolje koristiti funkciju pow
In [144]:
%time pow(45,33333333,342)
Out[144]:
Red od $a$ modulo $n$
red od 2 modulo 7 je jednak 3
In [145]:
sm.ntheory.n_order(2,7)
Out[145]:
red od 16 modulo 29 je jednak 7
In [146]:
sm.ntheory.n_order(16,29)
Out[146]:
red od 12 modulo 28 ne postoji
In [147]:
sm.ntheory.n_order(12,28)
Primitivni korijen modulo $p$
Svi primitivni korijeni modulo 7
In [148]:
list(filter(lambda x: sm.ntheory.is_primitive_root(x,7), range(1,7)))
Out[148]:
Svi primitivni korijeni modulo 41
In [149]:
list(filter(lambda x: sm.ntheory.is_primitive_root(x,41), range(1,41)))
Out[149]:
Svi primitivni korijeni modulo 23
In [150]:
list(filter(lambda x: sm.ntheory.is_primitive_root(x,23), range(1,23)))
Out[150]:
Svi primitivni korijeni modulo 50
In [151]:
list(filter(lambda x: sm.ntheory.is_primitive_root(x,50), reducirani_sustav_ostataka(50)))
Out[151]:
primitivni korijen modulo $n$ generira reducirani sustav ostataka modulo $n$
In [152]:
reducirani_sustav_ostataka(23)
Out[152]:
In [153]:
[pow(5,k,23) for k in range(sm.ntheory.totient(23))]
Out[153]:
In [154]:
reducirani_sustav_ostataka(50)
Out[154]:
In [155]:
[pow(3,k,50) for k in range(sm.ntheory.totient(50))]
Out[155]:
In [156]:
[pow(37,k,50) for k in range(sm.ntheory.totient(50))]
Out[156]:
Nelinearne kongruencije
$x^5\equiv2\!\pmod{7}$
In [157]:
list(filter(lambda x: pow(x,5,7)==2, range(7)))
Out[157]:
$x^{12}\equiv37\!\pmod{41}$
In [158]:
list(filter(lambda x: pow(x,12,41)==37, range(41)))
Out[158]:
$7^x\equiv6\!\pmod{17}$
In [159]:
list(filter(lambda x: pow(7,x,17)==6, range(17)))
Out[159]:
$3^x\equiv2\!\pmod{23}$
In [160]:
list(filter(lambda x: pow(3,x,23)==2, range(23)))
Out[160]:
$2x^8\equiv5\!\pmod{13}$
In [161]:
list(filter(lambda x: 2*pow(x,8,13)%13==5, range(13)))
Out[161]:
$x^5\equiv2\!\pmod{12}$
In [162]:
list(filter(lambda x: pow(x,5,12)==2, range(12)))
Out[162]:
$x^5\equiv4\!\pmod{12}$
In [163]:
list(filter(lambda x: pow(x,5,12)==4, range(12)))
Out[163]:
Funkcija $\pi(x)$
In [164]:
sm.ntheory.primepi(100)
Out[164]:
In [165]:
sm.ntheory.primepi(10000)
Out[165]:
In [166]:
sm.ntheory.primepi(34.56)
Out[166]:
In [167]:
sm.ntheory.primepi(np.pi**100)
In [168]:
sm.ntheory.primepi(np.pi**15)
Out[168]:
In [169]:
DSTG.ispis([sm.ntheory.primepi(n) for n in range(1,50)],80)
In [170]:
DSTG.ispis([(n,sm.ntheory.primepi(n)) for n in range(1,50)],80)
Teorem o prostim brojevima
In [171]:
figure(figsize=(12,8))
prvi=[sm.ntheory.primepi(n) for n in range(1,101)]
grid(True)
plot(range(1,101),prvi,'.',markersize=12)
xlim([0,101])
ylim([-1,27]);
In [172]:
figure(figsize=(12,8))
grid(True)
xx=np.arange(1.1,100.01,0.01)
plot(xx,xx/np.log(xx),linewidth=3.0,c='r')
xlim([0,110])
ylim([0,27]);
In [173]:
figure(figsize=(12,8))
prvi=[sm.ntheory.primepi(n) for n in range(1,101)]
grid(True)
plot(range(1,101),prvi,'.',markersize=12)
xx=np.arange(1.1,100.01,0.01)
plot(xx,xx/np.log(xx),linewidth=3.0,c='r')
xlim([0,110])
ylim([-1,27])
xlim([0,101]);
In [174]:
def teorem_prosti_brojevi(n):
prvi=[sm.ntheory.primepi(k) for k in range(1,n+1)]
grid(True)
plot(range(1,n+1),prvi,'.',markersize=10)
xx=np.arange(1.1,n+0.01,0.01)
plot(xx,xx/np.log(xx),linewidth=3.0,c='r');
In [175]:
figure(figsize=(12,8))
teorem_prosti_brojevi(1000)
In [176]:
figure(figsize=(12,8))
teorem_prosti_brojevi(10000)
In [177]:
figure(figsize=(12,8))
teorem_prosti_brojevi(100000)
In [ ]: