Efektivní řešení rovnice 2^(263)=2+k*263

Vlastně ani není nutné příklad vypočítat, stačilo by mi nějakým způsobem dokázat, že k je přirozené číslo

Jinak se ta otázka dá také položit jako: Dokaž, že platí 2^(263)≡ 2(mod 263)

Důsledek malé fermatovy věty: 2^263 = 2 (mod 263) => 2^263 = 2 + k * 263

Podmínky už si zkontroluj sám.

Ano, tohle vím, ale já bych rád našel (s Vaší pomocí) nějaký způsob, jak určit, že k je přirozené číslo, tedy tím dokázat (s jistou pravděpodobností), že 263 je prvočíslo. Potřebuji nějak obejít ty zdlouhavé výpočty (dělit 2^263-2 dvěstě šedesáti třema).

Budu počítat modulo 263, ale nebudu to explicitně uvádět.

2^263 = 2^(256 + 7) = (2^8)^32 * 2^7

2^7 = 128 2^8 = 256 2^16 = 256 * 256 = 49 2^32 = 49 * 49 = 34 2^64 = 34 * 34 = 104 2^128 = 104 * 104 = 33 2^256 = 33 * 33 = 37 2^263 = 37 * 128 = 2

Moc se omlouvám,ale nemohl byste to prosím trochu více rozepsat, nejsem v této části vůbec zběhlý. Nemyslíte, že existuje nějaký jednodušší způsob. Slyšel jsem, že by mi mohla pomoci Eulerova funkce...

Eulerova funkce nepomůže, protože na její použití musíme znát rozklad čísla 263 na prvočísla, což se snažíme dokázat.

Ale nějak mi tu nesedí tyhle dotazy.

Psal jsi, že víš o důsledku fermatovy věty a dokonce jsi sám uvedl její znění, takže bych čekal, že budeš chápat význam eulerovy funkce?

Rozepsat se můžu, ale potřeboval bych vědět, s jakou matematikou pracujeme?

Ve výpočtu používám pouze umocňování a násobení, dobře, jsou to kongruence na celočíselném okruhu, ale to na mocninných úpravách nic nemění.

Jedná se alespoň o vysokoškolskou matematiku nebo je to nějaká práce na základku/střední školu?

Chápeš, jak funguje test přes Fermatovu větu a jaká je šance na nalezení prvočísla a selhání testu u pseudo-prvočísla?

Co se týká jednoduchosti, ukázal jsem, že číslo o 80 číslicích je kongruentní k 2 v osmi dílčích krocích!

Ne, nic jednoduššího (tímhle způsobem) opravdu není, pokud chceme používat jenom tužku a papír.

Kdyby bylo, nefungovala by moderní kryptografie.

A dovolím si k tomu poznámku, že pouštět se do prvočísel bez základních znalostí teorie čísel je velice špatný nápad.

Díky

Ano, snad je to velmi hloupé, pravděpodobně. Ale přesto Vás ještě budu obtěžovat otázkou: např. zde 2^16 = 256 * 256 = 49 2^32 = 49 * 49 = 34

Jak přesně přijdu na 49 nebo 34. Chápu, jestli se mi teď smějete, ale stejně tak věřím, že budete tak laskav a vysvětlíte mi, jak to je, ušetříte mi tím mnoho času nad knihami. Moc Vás prosím

Jsme na okruhu modulo 263, takže ze všeho nad 262 vezmeme zbytek po dělení 262 (modulo 263) = 262 263 (modulo 263) = 0 264 (modulo 263) = 1 265 (modulo 263) = 2

2^8 = 256 (modulo 263) = 256 2^16 = 2^(8 + 8) = 2^8 * 2^8 = 256 * 256 = 65536 (modulo 263) = 49 2^32 = 2^(16 + 16) = 2^16 * 2^16 = 49 * 49 = 2401 (modulo 263) = 34

Takže jednoduše počítáme kongruence a vždy použijeme hodnotu z předchozího řádku.

Jsou to jenom mocniny na druhou a násobení.

Pro mě takovéhle věci nejsou k smíchu, proto jsem se ptal na to, o jaké matematice mluvíme.

Ale ten čas nad knihami by byl dobře strávený.