Forum Sains Indonesia




*
Selamat datang, Pengunjung. Silahkan masuk atau mendaftar. Apakah anda lupa aktivasi email?
Mei 25, 2012, 02:04:59 PM

Masuk dengan nama pengguna, kata sandi dan lama sesi

Artikel Sains

Aku Cinta ForSa

  ForSa on FB  ForSa on Twitter

Pranala Luar

ShoutBox!

Last 10 Shouts:

 

fajri

Kemarin jam 09:40:03 PM
numpang liat_liat dulu,, kexnya menarik bnget sama masalah mikon.. ! :D
 

haman11

Kemarin jam 08:11:34 AM
ada yg tauproses daur ulang urin pada cicak gk ? ;)
 

GhostInMachine

Mei 23, 2012, 03:52:17 PM
kk mau tanya cara upload Tulisan dong??
 

army.fice

Mei 23, 2012, 12:22:47 AM
sepi banget sih :(
 

lustforscience

Mei 22, 2012, 08:26:02 PM
amin
 

exile_rstd

Mei 22, 2012, 08:24:55 PM
offline....
good night all  ;)
 

exile_rstd

Mei 22, 2012, 08:23:08 PM
iyaaaa jumat saya mau ujian kenaikan kelas. doain ya om Farabi, semoga ujiannya lancar dan dpt nilai memuaskan  :D
 

Farabi

Mei 22, 2012, 08:20:37 PM
KMana aja non? Sibuk belajar?
 

exile_rstd

Mei 22, 2012, 07:44:23 PM
argh lama ga buka forsa, comment di beberapa thread jd membingungkan saya. apa karena udh lama ga asah ya...
 

N E R R O

Mei 20, 2012, 07:41:57 PM
udah lama gak mampi ke forsa, sdh banyak berubah

Show 50 latest

Penulis Topik: Probable Prime  (Dibaca 7561 kali)

0 Anggota dan 1 Pengunjung sedang melihat topik ini.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Probable Prime
« pada: Oktober 18, 2008, 07:12:53 AM »
Menurut Little Fermat Theorem jika p bilangan prima maka untuk setiap bilangan bulat a berlaku a^p=a(mod p). Khususnya jika p tidak membagi habis a atau katakan p dan a relatif prima maka  a^(p-1)=1(mod p).
Teorema ini termasuk mudah pembuktiannya asal memahami binomial newton dan induksi matematik.
Okay kita tuliskan yang lebih terang, p prima ==> a^p=a(mod p)
Di sini konversnya (a^p=a(mod p) ==> p prima ) tidak berlaku artinya kalau p dan a memenuhi a^p=a(mod p) belum tentu p prima.
Bilangan p yang memenuhi a^p=a(mod p) biasa disebut dengan aPRP (probable prime base a), kemudian kalau ternyata bilangan p itu komposit maka disebut pseudoprime.
Contohnya :
5 termasuk 2-PRP karena 2^5=32=2(mod 5) karena 32=6x5+2
7 termasuk 2-PRP karena 2^7=128=2(mod 7) karena 128=18x7+2
9 bukan termasuk 2-PRP karena 2^9=512=56x9+8 tidak sama dengan 2(mod 9) jadi tidak termasuk 2-PRP
dst...semua bilangan prima akan memenuhinya.
tapi tidak semua yang memenuhi 2-PRP akan merupakan bilangan prima, yaitu contohnya
341 termasuk 2-PRP karena
2^341=4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231552=2(mod 341)
tapi 341=11x31 (komposit)
Jadi 341 ini termasuk pseudoprime. Ada beberapa tapi tak terhingga pseudoprime ini, maksudnya dalam rentang yang lumayan adanya. Berawal dari sinilah primality test yang lebih modern dikembangkan, sampai yang lebih modern lagi adalah dengan teori group terutama teorema lagrange dimana indeks suatu group berhingga merupakan hasil perkalian indeks subgroup dengan indeks quotient groupnya, dalam hal bilangan prima ini groupnya adalah Z bilangan asli dan subgroupnya adalah pZ. Dan sampai terbentur pada hipotesa Riemann. Mulai dari yang sederhana di atas silahkan dilanjutkan pembicaraan yang lebih dalam lagi seperti Strong Probable Prime base a (a-SPRP)



Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #1 pada: Oktober 22, 2008, 09:45:18 PM »
Weh lanjut sendiri dulu juga ini jadinya....
Untuk memahami a-SPRP (Strong Probable Prime base a) kita mulai dari sebuah lemma yang juga penting dalam matematika yang mendasari sistem kriptografi. Ini sebelum membahas tentang primitive root.
Berikut lemmanya : Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka ada suatu bilangan bulat positif n sehingga x^n=1(mod m).
Buktinya :
Kita dengan bukti yang tidak formal dulu yang mudah ditangkap, misalnya m=7, maka kelas-kelas kongruensi modulo 7 adalah :
{0,7,14,21,28,...} = {0(mod 7)}
{1,8,15,22,29,...} = {1(mod 7)}
{2,9,16,23,30,...} = {2(mod 7)}
{3,10,17,24,31,...} = {3(mod 7)}
{4,11,18,25,32,...} = {4(mod 7)}
{5,12,19,26,33,...} = {5(mod 7)}
{6,13,20,27,34,...} = {6(mod 7)}
Kita ambil misalnya x=4 dan x relatif prima terhadap 7, lalu kita lihat 4^3=64=9x7+1=1(mod 7).
Jadi di sini n=3. Kita bisa mencoba yang lain. Hanya perlu diketahui bahwa yang membuat 4^n=1(mod 7) tidak hanya n=3, contohnya n=6 karena 4^6=4096=585x7+1=1(mod 7). Kemudian n yang terkecil yang memenuhi  x^n=1(mod m) biasa disebut order kelas kongruensi modulo m terhadap x. Ini bukan bukti sebenarnya tapi saya kira lebih mudah untuk dipahami sebelum masuk yang betul-betuk niskala.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #2 pada: November 01, 2008, 05:53:47 AM »
Dilanjut lagi primanya...
Kayaknya belum ada yang berminat, padahal aplikasinya banyak nih..

{0,7,14,21,28,...} = {0(mod 7)}
{1,8,15,22,29,...} = {1(mod 7)}
{2,9,16,23,30,...} = {2(mod 7)}
{3,10,17,24,31,...} = {3(mod 7)}
{4,11,18,25,32,...} = {4(mod 7)}
{5,12,19,26,33,...} = {5(mod 7)}
{6,13,20,27,34,...} = {6(mod 7)}

2^1=2=2(mod 7),2^4=16=2(mod7),2^7=128=2(mod 7),...
2^2=4=4(mod 7),2^5=32=4(mod 7),2^8=256=4(mod 7),...
2^3=8=1(mod 7),2^6=64=1(mod 7),2^9=512=1(mod 7),...
Order kelas kengruensi 7 terhadap 2 adalah 3

3^1=3=3(mod 7),3^7=2187=3(mod 7),...
3^2=9=2(mod 7),3^8=6561=2(mod 7),...
3^3=27=6(mod 7),3^9=19683=6(mod 7),...
3^4=81=4(mod 7),3^10=59049=4(mod 7),...
3^5=243=5(mod 7),3^11=177147=5(mod 7),...
3^6=729=1(mod 7),3^12=531441=1(mod 7),...
Order kelas kengruensi 7 terhadap 3 adalah 6

4^1=4=4(mod 7),4^4=256=4(mod 7),...
4^2=16=2(mod 7),4^5=1024=2(mod 7),...
4^3=64=1(mod 7),4^6=4096=1(mod 7),...
Order kelas kengruensi 7 terhadap 4 adalah 3

5^1=5=5(mod 7),5^7=78125=5(mod 7),...
5^2=25=4(mod 7),5^8=390625=4(mod 7),...
5^3=125=6(mod 7),5^9=1953125=6(mod 7),...
5^4=625=2(mod 7),5^10=9765625=2(mod 7),...
5^5=3125=3(mod 7),5^11=48828125=3(mod 7),...
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6

6^1=6(mod 7),6^3=216=6(mod 7),...
6^2=36=1(mod 7),6^4=1296=1(mod 7),...
Order kelas kengruensi 7 terhadap 6 adalah 2


x=a(mod m) dengan 0<a<m
Ada k bilangan bulat sehingga
x=km+a ==> x^2=(km)^2+2kma+a^2=(mk^2+2ka)m+a^2 ==> x^2=a^2(mod m)
Dengan binomial newton, maka
x^n=Am+a^n=a^n(mod m), untuk suatu bilangan bulat A.
 
sehingga x^i=a^i(mod m) dan x^j=a^j(mod m) dengan 0<a<m.
Kapan terjadi x^i=x^j(mod m) ? Yaitu jika m|(x^j-x^i) atau
m|{x^i)}{x^(j-1)-1} dan karena x^i relatif prima terhadap m (x relatif prima terhadap m maka x^i relatif prima terhadap m), maka m|{x^(j-1)-1} ==> x^(j-i)=1(mod m) atau a^(j-i)=1(mod m)

Ini menghasilkan lemma yang kedua, yaitu :
Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #3 pada: November 06, 2008, 11:47:15 AM »
Lema tersebut kemudian dilanjutkan yang ketiga :
Jika p bilangan prima serta x dan y bilangan positif bulat yang keduanya relatif prima dengan p serta jika keduanya mempunyai order yang sama untuk kelas kongruensi modulo p, katakanlah ordernya d, maka ada bilangan bulat k yang relatif prima terhadap d sehingga y=x^k(mod p).

Nah.. dari sini lalu didefinisikan akar primitif. Misalkan m bilangan bulat positif, maka suatu bilangan bulat g dikatakan akar primitif modulo m jika untuk setiap bilangan bulat x yang relatif prima terhadap m, ada bilangan bulat j sehingga
x=g^j(mod m).

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #4 pada: November 09, 2008, 08:58:20 AM »
Ulasan mengenai lemma-lemma :

Pertama :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka ada suatu bilangan bulat positif n sehingga x^n=1(mod m)."

Contoh :
m=3, x=5 maka 5^1=5=2(mod 3), 5^2=25=1(mod 3) inilah karena 3 dan 5 relatif prima maka ada n=2 shg 5^2=1(mod 3)
m=5, x=10 maka 10^1=10=0(mod 5),10^2=100=0(mod 5), kita tahu untuk selanjutnya selalu merupakan 0(mod 5) jadi tak ada dong n yang memenuhi 5^n=1(mod 5) inilah karena 5 dan 10 tidak relatif prima.
m=6, x=8 maka 8^1=8=2(mod 6),8^2=64=4(mod 6),8^3=512=2(mod 6),8^4=4096=4(mod 6), dst ini selalu berselang-seling antara 2(mod 6) dan 4(mod6) dan bisa dibuktikan dengan induksi yaitu 8^n-2 habis dibagi 6 jika n ganjil dan 8^n-4 habis dibagi 6 jika n genap. Inilah karena 6 dan 8 tidak relatif prima.

Jika m bilangan prima maka untuk x bilangan asli dibawah m akan selalu relatif prima terhadap m,
contohnya jika m=7, maka 1,2,3,4,5,dan 6 relatif prima terhadap 7.
Jadi untuk m bilangan prima, maka untuk semua x lebih kecil dari m, akan selalu ada n sehingga x^n=1(mod m)

Kedua :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x."

Kita lihat pada contoh kelas-kelas kongruensi modulo 7 di atas, yakni m=7 dan x=5 :
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6
Kalau kita teruskan maka 5^6, 5^12, 5^18, 5^24,... semuanya merupakan 1(mod7). Jadi ambilah 5^6=15625 dan 5^18=3814697265625
dan 5^18-5^6 = 3814697250000 = 544956750000 x 7 sehingga 5^18=5^6(mod 7) dan kita lihat j=18 dan i=6 sehingga j=i(mod 6), di sini 6 merupakan order kelas kongruensi modulo 7 terhadap 6.
Lebih lanjut lemma ini juga menjamin bahwa jika x^i=x^j(mod m) maka x^i dan x^j berada pada kelas yang sama. Karena untuk semua x bilangan bulat positif di bawah m relatif prima terhadap m jika m prima, maka berarti kelas kongruensi modulo 7 - nya berlain-lainan (distinct)

Ketiga :
"Jika p bilangan prima serta x dan y bilangan positif bulat yang keduanya relatif prima dengan p serta jika keduanya mempunyai order yang sama untuk kelas kongruensi modulo p, katakanlah ordernya d, maka ada bilangan bulat k yang relatif prima terhadap d sehingga y=x^k(mod p)."

Kita ganti simbol m menjadi p untuk mulai memastikan bahwa kita bekerja pada bilangan prima. Kita ambil contoh p=7 serta x dan y masing-masing 5^6=15625 dan 5^18=3814697265625 dan keduanya ini kita tahu relatif prima terhadap 7 (bisa dibuktikan dengan induksi bahwa jika x relatif prima terhadap p maka x^n relatif prima terhadap p). Keduanya berorder d=6 atas kelas kongruensi modulo 7. Maka kita lihat 5^18=5^6(mod 7) ==> 5^18=(5^6)^5(mod 7), disini k=5 relatif prima terhadap d=6. Bisa dihitung bahwa 5^30-5^18 = 931322574615478515625-3814697265625 = 931322570800781250000 = 133046081542968750000 x 7.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #5 pada: November 12, 2008, 12:55:37 PM »
Berikut bukti formal lemma, saya kira yang bisa memahami orang-orang dari matematika atau fisika. Lemma yang pertama dulu.

Lemma 1 :
Taruhlah m bilangan bulat positif, dan x adalah bilangan bulat yang relatif prima terhadap m. Maka ada bilangan bulat positif n sedemikian hingga x^n=1(mod m).

Bukti :
Kelas-kelas kongruensi modulo m banyaknya berhingga, yaitu sebanyak m :
{0(mod m)}, {1(mod m)}, {2(mod m)},. . ., {m-1(mod m)}
Setiap bilangan bulat pasti menjadi anggota dari salah satu kelas-kelas kongruensi tersebut.
Maka kita bisa memilih i dan j sehingga x^i=x^j(mod m) dengan i<j. Mungkin ini agak membingungkan mengapa bisa demikian, kita lihat lagi bahwa kelas-kelas kongruensi tersebut bisa dituliskan dengan :
{km}, {km+1}, {km+2},..., {km+m-1}
Misalkan x^i anggota {km+q} dengan 0=<q<m, maka pada langkah-langkah berikutnya tentu terdapat x^j anggota {km+q}.
Sebagai contoh, 8^3=512=2(mod 17), lalu 8^11=8589934592=2(mod 17), sehingga 8^3=8^11(mod 17).
Untuk generalnya, sebagai berikut :
Asumsikan tidak ada j>i sehingga x^i=x^j(mod m) berarti misalkan x^i=q(mod m) dengan 0=<q<m, maka untuk semua j>i berlaku x^j<>q(mod m), taruhlah x^i=km+q untuk suatu bilangan bulat positif k, maka (x^i)^2=(km)^2+2kmq+q^2=(mk^2+2kq)m+q^2=q^2(mod m) dan dapat ditunjukkan dengan binomial newton bahwa (x^i)^m=q^m(mod m).
Kita perhatikan bahwa menurut teorema Fermat Kecil maka q^m=q(mod m) atau dengan kata lain m membagi habis (q^m-q). Jadi q^m = (q^m-q) + q = q(mod m). Sehingga asumsi kita gagal karena dengan mengambil j=im, maka x^j=x^(im)=(x^i)^m=q^m(mod m)=q(mod m).
Karena itu Kita bisa menaruh x^j=x^i(mod m) atau x^i=x^j(mod m)
Taruhlah n=j-i maka (x^i)(x^n)=(x^i)(mod m)
Karena x relatif prima terhadap m, maka ada a dan b sehingga ax + bm = 1 ==> ax=1-bm ==> (ax)^i=(1-bm)^i
==> (a^i)(x^i) = 1 + Hm untuk suatu bilangan bulat H ==> (a^i)(x^i) - Hm = 1 sampai disini kombinasi linear ini memberikan arti bahwa x^i dan m relatif prima. Akhirnya kita bisa melakukan kanselasi yang menjadikan (x^n)=1(mod m). Terbukti.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #6 pada: November 15, 2008, 07:34:21 AM »
Sebaiknya juga kutuliskan bukti Little Fermat Theorem berikut :

Taruhlah p sebuah bilangan prima. Maka x^p=x(mod p) untuk semua bilangan bulat x. Lebih lanjut jika x relatif prima terhadap p maka x^(p-1)=1(mod p).

Sebelumnya kita buktikan lemma berikut sebagai pendahuluannya :
Lemma :
Taruhlah p bilangan prima. Maka koefisien binomial C(p,k) habis dibagi p untuk semua bilangan bulat k yang memenuhi 0 < k < p.
Bukti :
Koefisien binomial diberikan dengan formula C(p,k)=p!/{(p-k)!k!}
Jika 0<k<p maka C(p,k) = [p(p-1)!] / [(p-k)!k!] = pm / k! dengan m=(p-1)! / (p-k)!. Sehingga (k!)C(p,k) = pm, maka k! membagi habis pm. Juga karena k! relatif prima terhadap p, ini dikarenakan p prima dan semua bilangan positif lebih dari 1 dan kurang dari p akan relatif prima ternadap q.
{ jika a dan p relatif prima juga b dan p relatif prima maka ab relatif prima terhadap p, karena jika ada g,h,i,j bilangan bulat sehingga ga+hp=1 juga ib+jp=1 maka (ga)(ib)=(1-hp)(1-jp)=1-(h+j)p+hjp^2 ==> (gi)ab + (h+j-hjp)p=1 }
Karena k! membagi habis pm dan k! relatif prima terhadap p maka haruslah k! membagi habis m. Sehingga koefisien binomial C(p,k) merupakan kelipatan p. Terbukti.

Bukti Teorema Fermat :
Taruhlah p prima maka (x+1)^p=Sigma(dari k=0 ke p) C(p,k)x^k
Menurut lemma di atas maka (x+1)^p=(x^p+1)(mod p). Sehingga jika f(x)=x^p-x maka
f(x+1)(mod p)=(x^p+1)(mod p) - (x+1)(mod p)
  f(x)(mod p)=(x^p)(mod p) - x(mod p)
___________________________________________  -
f(x+1)(mod p) - f(x)(mod p) = 1(mod p) - 1(mod p) = 0(mod p)
==> f(x+1)=f(x)(mod p)

Jadi f(x+1)=f(x)(mod p) untuk semua bilangan bulat x.
Karena f(0)=0^p-0=0(mod p) maka
f(1)=f(0+1)=f(0)(mod d)=0(mod p),
f(2)=f(1+1)=f(1)(mod p)=0(mod p),
f(3)=f(2+1)=f(2)(mod p)=0(mod p),
dst dengan induksi... jadi untuk semua x positif f(x)=0(mod p).

Kita bergerak pada bilangan bulat, jadi karena f(x+1)=f(x)(mod p) maka f(x)=f(x+1)(mod p), lalu
f(0)=f(-1+1)(mod p)=f(-1) dan f(0)=0(mod p) ==> f(-1)=0(mod p),
f(-1)=f(-2+1)(mod p)=f(-2)(mod p) dan f(-1)=0(mod p) ==> f(-2)=0(mod p),
f(-2)=f(-3+1)(mod p)=f(-3)(mod p) dan f(-2)=0(mod p) ==> f(-3)=0(mod p),
dst dengan induksi... jadi untuk semua x negatif f(x)=0(mod p).

Jadi untuk semua bilangan bulat f(x)=0(mod p).
Berarti x^p-x=0(mod p) ==> x^p=x(mod p), Untuk mana x relatif prima terhadap p, maka kita bisa
melakukan kanselasi (x^p)/x=1(mod p) ==> (x^(p-1))=1(mod p). Terbukti.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #7 pada: November 16, 2008, 08:20:22 AM »
Bukti Formal Lemma Kedua :

Taruhlah m bilangan bulat positif, dan x bilangan bulat yang relatif prima terhadap m, serta i dan j bilangan bilangan-bilangan bulat positif. Maka (x^i)=(x^j)(mod m) jika dan hanya jika i=j(mod d) dimana d adalah order kelas kongruensi modulo m terhadap x.

Bukti :
Kita akan membuktikan biimplikasi (x^i)=(x^j)(mod m) <==> i=j(mod d)
Kita bisa memilih i<j dan ini tidak menyebabkan lepas dari generalitasnya.

Pertama kita buktikan i=j(mod d) ==> (x^i)=(x^j)(mod m) :
Jika i=j(mod d) maka d | (j-i) ata ada bilangan bulat b sehingga (j-i)=bd, sehingga karena x^d=1(mod m) [ingat bahwa d adalah order kelas kongruensi modulo m terhadap x] dan misalkan x^d=km+1 kemudian (x^(j-i))=x^(bd)=(x^d)^b=(km+1)^b=Lm+1=1(mod m) untuk suatu L bilangan bulat. Sehingga x^j=(x^i)(x^(j-i))=(x^i)(1(mod m)) ==> (x^j)=(x^i)(mod m).

Kedua kita buktikan (x^i)=(x^j)(mod m) atau (x^j)=(x^i)(mod m) ==> i=j(mod d) :
Kita telah memilih i < j, maka (x^i)(x^(j-i))=(x^i)(mod m) dan karena x relatif prima terhadap m, sehingga x^i relatif prima terhadap m, ini menjadikan x^(j-i)=1(mod m). Sehingga jika d order kelas kongruensi modulo m terhadap x maka x^d=1(mod m). Kemudian misalkan j-i=kd+r dengan 0 =< r< d maka x^(j-i) = x^(kd+r) = ((x^d)^k)(x^r) = 1(mod m)
==> (x^r)=1(mod m). Ehh tapi d adalah order dari kelas modulo m terhadap x jadi harusnya d yang terkecil sehingga (x^d)=1(mod m), kalau ternyata (x^r)=1(mod m) dengan 0 =< r< d maka harusnya r=0 dan terbukti bahwa
d|(j-i) atau j=i(mod d). Terbukti.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #8 pada: Desember 05, 2008, 01:58:23 PM »
Ternyata memang belum ada yang begitu berminat atau terlalu susah dipahami yaa, tapi saya rasa orang2 matematika terutama yang master atau yang pernah belajar kriptografi pernah membacanya kalo ada di forum ini.
Disini untuk memahami bukti lemma ketiga dibutuhkan prasyarat lebih terutama pemahaman tentang penyelesaian suku banyak kongruensi modulo n. Saya belum menemukan cara yang mangkus untuk membuatnya jadi jelas. Melangkah dari konkrit ke abstrak memang membutuhkan energi pikiran.

Offline mkukuh

  • Mahasiswa
  • **
  • Tulisan: 14
  • IQ: 6
    • Lihat Profil
Re: Probable Prime
« Jawab #9 pada: Desember 29, 2008, 02:35:22 AM »
salam kenal kerajaan mataram
saya kukuh..newbie ni
saya baru nemu situs ni pas dini hari..tak bobok dulu ya..
o y saya tertarik ntar tak pelajari dulu...ok pak asisten dosen/dosen.
jangan pernah kesepian yo...salam

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #10 pada: Januari 05, 2009, 09:04:38 PM »
Salam saudara mkukuh, topik ini adalah pada teori bilangan elementer yaitu tentang primitive root, senang bisa berdialog. Saya bukan dosen dari suatu institusi, hanya seorang praktisi komputer berlatar belakang matematika. Karena melihat teori bilangan bermain disini maka saya ublek2.

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #11 pada: Pebruari 10, 2009, 09:30:57 PM »
Oke biar kuhangatkan lagi biar tidak usang digulung tempat terus...karena topik ini termasuk menarik sekaligus pelik.

Kita putar balik dulu pada kongruensi persamaan polinomial dan fungsi Euler..supaya tidak menjendel di jalan.

Fungsi Euler dulu lah..

Taruhlah n bilangan bulat positif. Kita definisikan \Psi(n) sebagai banyaknya bilangan bulat x yang memenuhi
0 =< x < n yang relatif prima terhadap n. Fungsi Xi pada himpunan bilangan bulat positif kita sebut sebagai
fungsi Euler.

Setiap bilangan bulat (termasuk nol) relatif prima terhadap 1, karena itu \Psi(1)=1.
Taruhlah p bilangan prima. Maka \Psi(p)=p-1, karena setiap bilangan bulat positif kurang dari p akan relatif
prima terhadap p. Lebih lanjut \Psi(p^k)=(p^k)-(p^{k-1}) untuk semua bilangan bulat positif k, karena bilangan
bulat yang memenuhi 0\le x \le p^k yang habis dibagi p ada sebanyak p^{k-1}, dan bilangan bulat yang relatif
prima terhadap p adalah yang selain habis dibagi p.
Contoh :
p=5 ==> \Psi(5)=4, yaitu {1,2,3,4}
p^2=25 ==>\Psi(25)=5^2-5^1=20, yaitu {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24}
     yang habis dibagi 5 adalah {5,10,15,20,25} sebanyak 5

Secara general untuk p^k :
Bilangan bulat positif yang habis dibagi p dari 1 s.d. p^2 adalah p,2p,3p,...,p^2 ==> sebanyak p
Bilangan bulat positif yang habis dibagi p dari p^2+1 s.d. 2p^2p^2+1 s.d. 2p^2 adalah p^2+p,p^2+2p,...,2p^2 adalah p^2+p,p^2+2p,...,2p^2 ==> sebanyak p
Bilangan bulat positif yang habis dibagi p dari 2p^2+1 s.d. 3p^2 adalah 2p^2+p,2p^2+2p,...,3p^2 ==> sebanyak p
...........
...........
Bilangan bulat positif yang habis dibagi p dari (p-1)p^2+1 s.d. p^3 adalah (p-1)p^2+p,(p-1)p^2+2p,...,p^3 ==> sebanyak p
[sampai disini yang habis dibagi p sebanyak p^2]
Bilangan bulat positif yang habis dibagi p dari p^3+1 s.d. p^3+p^2 adalah p^3+p,p^3+2p,...,p^3+p^2 ==> sebanyak p
..........
..........
dan seterusnya....
akhirnya yang habis dibagi p sebanyak p^{k-1}

Masih berlanjut .... nulisnya cukup ngoyo ini...tapi yang penting bisa bermanfaat.


Offline nandaz

  • Profesor
  • *****
  • Tulisan: 1836
  • IQ: 110
  • Gender: Pria
  • ...Mad about Sci_mistery
    • Lihat Profil
Re: Probable Prime
« Jawab #12 pada: Pebruari 11, 2009, 02:39:13 PM »
waw, rumit... hebat sekali!!!  (sebetulnya ngga ngerti sih...)

starting by doing what is necessary, then what is possible and suddenly you are doing the impossible...
\dia\cal{ANONYMOUS}\cl

Offline Mtk Kerajaan Mataram

  • Profesor
  • *****
  • Tulisan: 504
  • IQ: 54
  • Gender: Pria
    • Lihat Profil
Re: Probable Prime
« Jawab #13 pada: Pebruari 13, 2009, 11:01:04 PM »
Yaa memang rumit...biasanya dalam literatur-literatur hanya disingkat penjelasannya, semoga uraian ini bisa membawa titik terang.

Jadi kemarin dari 1 sampai dengan pk ada sebanyak pk-1 bilangan yang habis dibagi dengan p dengan kata lain karena p-nya prima maka ada sebanyak pk-1 bilangan yang tidak relatif prima terhadap pk dan lalu berarti ada sebanyak pk-pk-1 bilangan dari 1 sampai dengan pk yang relatif prima terhadap pk.

Lalu berapa banyaknya bilangan dari 1 s.d. paqb yang relatif prima terhadap paqb dengan p dan q keduanya prima ?

Yang tidak relatif prima terhadap pa sebanyak pa-1 dari 1 s.d. pa,
Yang tidak relatif prima terhadap qb sebanyak qb-1 dari 1 s.d. qb.
tidak relatif prima terhadap pa atau terhadap qb berarti juga tidak relatif prima terhadap paqb.

1,2, ..., paqb
= 1,2,...,pa,   
  pa+1,pa+2,...,pa+pa,
  .................
  [q-1]pa+1,[q-1]pa+2,...,qpa,
  ..................
  [qb-1]pa+1,[qb-1]pa+2,...,[qb]pa.

Tunjukkan bahwa banyaknya bilangan yang relatif prima terhadap paqb adalah [pa-pa-1][qb-qb-1] ....

Offline ryoma

  • Profesor
  • *****
  • Tulisan: 419
  • IQ: 16
  • Gender: Pria
  • i am not lucky, just a hope, calm, and happy..!
    • Lihat Profil
    • Jurnal Milzam
Re: Probable Prime
« Jawab #14 pada: Pebruari 14, 2009, 09:02:23 AM »
waw, rumit... hebat sekali!!!  (sebetulnya ngga ngerti sih...)




walah-walah..
When there is a will there is a way..
قل حو الله الحد

 

Copyright © 2006-2011 Forum Sains Indonesia