|
|
|
[874] Gábor1905 | 2009-03-26 22:14:46 |
Üdv! Csak azt szeretném kérdezni hogy szerintetek gimis matekkal bizonyítható-e a Fermat sejtés n=3 esete?Szerintem sikerült csak még nem írtam le!:D:D:D
|
|
[873] jenei.attila | 2009-03-23 17:11:37 |
Továbbra is úgy értelmezem a kérdést, hogy "Hány olyan elem van 64 elemű testben, amely nincs benne valódi résztestben?" Ennek a testnek valóban csak 2,4 és 8 elemű résztestei lehetnek mivel minden test vektortér bármelyik részteste felett, ahogy Fálesz Mihály is írta. Ilyen résztestei pedig valóban vannak is, mégpedig mindegyikből csak 1-1. Ez a test (GF(64)) a x64-x polinomnak felbontási teste (e testben lineáris gyöktényezők szorzatára bomlik), sőt pontosan a x64-x polinom gyökei alkotják a test elemeit. Az, hogy ennek a testnek van 2, 4 és 8 elemű részteste abból következik, hogy a x2-x, x4-x és x8-x polinomok osztói a x64-x polinomnak, amelyek gyökei így szintén GF(64) elemei. Ezek a gyökök könnyen bizonyíthatóan résztesteket alkotnak, mert (x+y)2=x+y,(xy)2=xy,(-x)2=-x,(x-1)2=x-1 (itt kihasználtuk, hogy a test 2 karakterisztikájú). Hasonlóan 4 és 8 kitevővel. Más 2, 4 és 8 elemű résztestei GF(64)-nek nincsenek, mint a most felsorolt polinomok gyökeiből álló testek, mert az azt jelentené hogy a x2-x, x4-x és x8-x polinomoknak 2,4 illetve 8-nál több gyökük lenne ami lehetetlen. A 2 elemű (0,1 -et tartalmazó) résztest részteste a 4 és 8 elemű testeknek is, azonban a 4 elemű résztest nem részteste a 8 eleműnek (mivel a 8 elemű test nem lehet vektortér a 4 elemű felett). Vagyis e résztestek uniója 10 elemet tartalmaz, a maradék 54 elem pedig egyik résztestnek sem eleme.
|
Előzmény: [862] Bubcsi, 2009-03-17 11:01:41 |
|
[872] lgdt | 2009-03-20 02:17:01 |
A Wikipedia szerint ez egy ismert probléma, amelyre eddig nem találtak polinom futásidejű algoritmust, és azt sem tudják, hogy van-e; viszont az inverzét, a hatványozást könnyű hatékonyan elvégezni. Ha jól tudom, az sem ismert, hogy léteznek-e bizonyítottan ilyen tulajdonságú ún. csapóajtófüggvények.
The existence of one-way functions
|
Előzmény: [867] Borel, 2009-03-18 19:25:53 |
|
|
[870] Borel | 2009-03-18 21:47:08 |
Köszönöm a válaszokat. Én is így számoltam eddig, csakhát reméltem van valami hatékonyabb megoldás is... n=7-re a 3 rendjéért már meg kell szenvedni (szg. nélkül).
|
Előzmény: [869] Tibixe, 2009-03-18 21:03:47 |
|
[869] Tibixe | 2009-03-18 21:03:47 |
Végignézheted szép sorban bd-t minden szóba jöhető d-re, azaz amikor d poz. egész és osztja (n)-t, aztán ha 1 maradékot ad, akkor az aktuális d lesz a válasz. Kis n-re ez is jó.
|
Előzmény: [867] Borel, 2009-03-18 19:25:53 |
|
[868] R.R King | 2009-03-18 20:26:50 |
Üdv. Freud: Számelmélet című könyvében pl. utána lehet nézni, de a google is segíthet:) a rend emlékeim szerint a legkisebb ,,jó'' kitevő és osztója minden jó kitevőnek pl. fi(n)-nek is. fi(n) n-ig az n hez relatív prímek száma. Konkrét b és n esetén tehát a rend a fi(n) osztói közül kerül ki. Régen tanultam ezekről talán diszkrét logaritmus(index) címszóval keresd a problémát.
|
Előzmény: [867] Borel, 2009-03-18 19:25:53 |
|