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

Dobrý den,

chtěl bych Vás všechny poprosit o radu, jak vypočítat co nejrychleji jen s tužkou a papírem příklad 2^(263)=2+k*263. Píši o způsobech určování prvočíselnosti, a toto by se mi moc hodilo...Děkuji moc! Daniel R.

✓   Téma bylo vyřešeno.
Daniel R.

Daniel R.

29. 12. 2015   22:53

8 odpovědí

Daniel R.
Daniel R.
29.12.2015 16:17:39

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)

Tomáš B.
Tomáš B.
29.12.2015 16:47:23

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

Podmínky už si zkontroluj sám.

Daniel R.
Daniel R.
29.12.2015 19:07:13

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).

Tomáš B.
Tomáš B.
29.12.2015 19:35:02

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

Daniel R.
Daniel R.
29.12.2015 20:03:31

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...

Tomáš B.
Tomáš B.
29.12.2015 21:51:04

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.

Daniel R.
Daniel R.
29.12.2015 22:35:05

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

Tomáš B.
Tomáš B.
29.12.2015 22:53:07

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ý.

Pro napsání komentáře se musíte přihlásit.