Lukuteoriasta

Seuraa 
Viestejä979
Liittynyt27.8.2007

Perus kongruenssilaskenta on kyllä hallussa, mutta vähän vaikeammissa asioissa onkin sitten ongelmia.

esim. 2^x = 10 mod(131)

Varmasti simppeli tehtävä, jos tietää miten homma tehdään. Eli kertokaa, mikä on tyypillinen käsittelytapa tuollaisissa tehtävissä.

" sähkö (se sähkö, jota tuotetaan mm. voimalaitoksissa) ei ole energiaa "
- Vastaaja_s24fi

“Jos et ole kaksikymppisenä vihreä, sinulla ei ole sydäntä. Mutta jos et ole nelikymppisenä perussuomalainen, sinulla ei ole aivoja.”
- Cargo

Kommentit (7)

Vierailija
Perus kongruenssilaskenta on kyllä hallussa, mutta vähän vaikeammissa asioissa onkin sitten ongelmia.

esim. 2^x = 10 mod(131)

Varmasti simppeli tehtävä, jos tietää miten homma tehdään. Eli kertokaa, mikä on tyypillinen käsittelytapa tuollaisissa tehtävissä.

En jaksa miettiä, mutta Fermat'n pienestä lauseesta
on varmaan apua. Huomaa, että 131 on alkuluku.

Ja saattaa olla myös hyötyä huomata, että: 10 = 2^3 + 2. Edit. ehkä

Cargo
Seuraa 
Viestejä979
Liittynyt27.8.2007

Miksei palstan matikka-perse Gödel ole nyt täällä jakelemassa viisauttaan?

Aika onneton "Tiede" foorumi Suomessa, jos tulee nollat tauluun koko jengillä yksinkertaisen näköisen laskun edessä......

" sähkö (se sähkö, jota tuotetaan mm. voimalaitoksissa) ei ole energiaa "
- Vastaaja_s24fi

“Jos et ole kaksikymppisenä vihreä, sinulla ei ole sydäntä. Mutta jos et ole nelikymppisenä perussuomalainen, sinulla ei ole aivoja.”
- Cargo

pöhl
Seuraa 
Viestejä875
Liittynyt19.3.2005

Niin. Onhan se aika onnetonta, jos ei osaa ratkaista tehtävää, johon ei tunneta tehokasta ratkaisutapaa. Aika erikoista kysyä ensin apua ja haukkua sitten muita kun muutkaan eivät osaa. Kokeilemalla nähdään, että x=47 on eräs ratkaisu.

Vierailija
Cargo
Aika onneton "Tiede" foorumi Suomessa, jos tulee nollat tauluun koko jengillä yksinkertaisen näköisen laskun edessä......

No jaa. Se, että jokin näyttää yksinkertaiselta, ei kyllä ole mikään tae siitä, että kyseessä olisi jotain yksinkertaista. Esimerkiksi Fermat'n suuri lause ei näytä mitenkään kummoiselta, mutta sen todistaminen onkin sitten aivan toinen juttu.

2^x = 10 mod(131)

Taisipa muuten olla niin, että tuon tyyliset kongruenssit ovat niin vaikeita ratkaista, että niihin perustuvia salausmenetelmiäkin on kehitetty. Esimerkiksi El Gamal pohjautuu diskreetin logaritmin ongelmaan.

Vierailija

Tällaisessa tehtävässä on ensin tarkistettava, onko 2 multiplikatiivisen ryhmän Z_131* generaattori, toisin sanoen onko luku 130 pienin sellainen luku, että 2^130=1(mod131). Koska 2:n generoima ryhmä on alkuperäisen ryhmän aliryhmä, niin 2:n kertaluku on jokin luvun 130 tekijöista, elikkäs jokin luvuista 2, 5 tai 13. Siis on tarkistettava, onko jokin potensseista 2^2, 2^5, 2^13, 2^10,2^26 tai 2^65 kongruentti yhden kanssa mod 131. Pitkähköillä laskuilla havaitaan, että ainoa, jolle 2^k = 1 (mod 131) on juuri 130, siis 2 on generaattori. Nyt voikin turvallisin mielin laskeskella kakkosen potensseja ja havaita, että 2^47=10 (mod 131). Yksinkertaisempaa tapaa en tiedä, näin meille ainakin lukuteoriassa/ algebrassa on näitä opetettu laskemaan. Toivottavasti saat edes jotain selkoa

Uusimmat

Suosituimmat