Matematické Fórum

HELLER · 04. 01. 2012 13:57

Ahoj, setkal jsem se se zdánlivě triviálním příkladem, který mi ale na základě skript nevychází
ve skriptech je že $15^{3300} = 4509 (mod 6601)$

Mě ale při výpočtu vychází 59337 (nejprve umocním 15 na 3300 poté vypočítám výsledek mod 6601)

Za odpověď předem díky.

vanok · 04. 01. 2012 15:32

Ahoj ↑ HELLER:,
Ak si vsimnes ze $6601=7*23*41$
tvoj problemsa znacne zjednodusi.

A naviac ani nemusis robit take otrocke vypocty ako pises.

HELLER · 04. 01. 2012 15:39

↑ vanok:
Ahoj, trošku nechápu, mohl bys mi pls vysvětlit k čemu je podobný rozklad?

vanok · 04. 01. 2012 15:59

↑ HELLER:,
ak dokazes ze mas
$15^{3300} = 4509 (mod p_i)$ pre kazde z prvocisiel
$p_1=7$ ...;
Bez vela teorie mas z toho
$15^{3300} -4509 =7k_1$
$15^{3300} -4509 =23k_2$
$15^{3300} -4509 =41k_3$

A z toho jednoducho mame ze (dokaz to sam)
$15^{3300} -4509 =7*23*41 k_4$ .... $k_i$ su cele konstanty

A to je vlastne tvoj vysledok.

Poznamka: je celkom mozne ze v skolme ste dokazali takyto vseobecny vysledok, potom mozes ist rychlejsie vo tvojom cviceni.

HELLER · 05. 01. 2012 00:17

↑ vanok:
Aha, nezlob se, asi jsem se trochu špatně zeptal. Jedná se o vzorec v rámci pravděpodobnostního algoritmu na určování prvočíselnosti (Lehmann - Peralta test). v něm máš počítat číslo di na základě vzorce $d_{i} = a_{i}^{p-1} mod p$ S tím, že ai je náhodně zvolené číslo 1 < ai < p . p je číslo testované na prvočíselnost. Zkoušel jsem jednoduše dosadit do vzorce (implementoval jsem to v javě), ale vychází mi čísla trochu mimo.

vanok · 05. 01. 2012 05:12

↑ HELLER:,

Zial ten test (Lehmann - Peralta ) nepoznam.
Ak su tvoje skripta na web, napis a mozno najdem cas aby som to pozrel podrobnejsie.
Asi malo ist o ukazku ako ten test zlyha ked miesto p mas zlozene cislo?

Ake aspon tvoj inicialny problem na tomto post je vyrieseny.

Matematické Fórum

#1 04. 01. 2012 13:57

Výsledek výrazu - modulo

#2 04. 01. 2012 15:32

Re: Výsledek výrazu - modulo

#3 04. 01. 2012 15:39

Re: Výsledek výrazu - modulo

#4 04. 01. 2012 15:59

Re: Výsledek výrazu - modulo

#5 05. 01. 2012 00:17

Re: Výsledek výrazu - modulo

#6 05. 01. 2012 05:12

Re: Výsledek výrazu - modulo

Zápatí