Matematické Fórum

Kedrigern

Ahoj,

potřeboval bych poradit s modulární reprezentací čísla, tady jí mám definovanou..

Převod z U do $[u_1 , \ldots, u_n]$ je jasný.

Trápí mě převod opačný. Díky zbytkové větě dostanu jednoznačnost a vím, že je to číslo menší než: $m_1 \cdot \ldots \cdot m_n$ , zde dokonce nacházím algoritmus pro převod.

Nicméně jeden krok mi selhává. Když se použije extended GCD, tak mě skoro vždy vyjde e_i záporné. A s tím se pak něco musí dělat, ne? Někde jsem našel, že pak použiji $u_i \cdot u_i^{-1} \cdot |e_i|$ namísto $u_i \cdot e_i$ , kde $u_i^{-1}$ je prvek inverzní v daném modulu.

Pokud e_i vyjde kladné jako v ukázkovém příkladu na Wiki, tak je vše ok. Docela rád bych znal odpovědi jak na to s těmi zápornými čísly, jelikož to se může stát vždy (ale většinu případů jde eliminovat mírným upravením EGCD)

Příklad 1:
Dostanu: $U = [1,3,1]\ \mathrm{pro}\ m_1 = 3 \mathrm{; }\ m_2 = 4 \mathrm{;}\ m_3 =5.\ N:= \prod m_i = 60$
Vypočítám e_i pomocí EGCD: $3x + 20y =1\ \Rightarrow\ x=7;\ y=-1\ \Rightarrow e_1 = |-20|\cdot1\cdot1=20\nl 4x+15y = 1\ \Rightarrow\ x=4\ ;\ y=-1\ \Rightarrow\ e_2= |-15|\cdot3\cdot3=135\nl 5x+12y=1\ \Rightarrow\ x=5\ ;\ y=-2\ \Rightarrow\ e_3=|-12|\cdot1 \cdot 1 = 12$ tedy $U=20+135+12=[167]_{60}=47$ Což není správný výsledek 47%3=2

Příklad 2 (ten z Wiki):
Dostanu: $U = [2,3,1]\ \mathrm{pro}\ m_1 = 3 \mathrm{; }\ m_2 = 4 \mathrm{;}\ m_3 =5.\ N:= \prod m_i = 60$
Vypočítám e_i pomocí EGCD: $3x + 20y =1\ \Rightarrow\ x=7;\ y=-1\ \Rightarrow e_1 = |-20|\cdot2\cdot3=240\nl 4x+15y = 1\ \Rightarrow\ x=4\ ;\ y=-1\ \Rightarrow\ e_2= |-15|\cdot3\cdot3=135\nl 5x+12y=1\ \Rightarrow\ x=5\ ;\ y=-2\ \Rightarrow\ e_3=|-12|\cdot1 \cdot 1 = 12$ tedy $U=240+135+12=[387]_{60}=27$ Což není správný výsledek 27%3=0

Předem děkuji za odpovědi.

Kondr · 09. 06. 2010 16:05

K prvnímu příkladu:
Oni tam počítají $e_i=s_iN/n_i$ , příčemž $s_i$ jsou ta tvoje $y$ a $N/n_i$ jsou po řadě 20,15,12. Potom $e_1=-20$ , $e_2=-15$ , $e_3=-24$ . Pak $\sum a_ie_i=1\cdot(-20)+3\cdot(-15)+1\cdot(-24)=-89$ , po dělení 120 tedy 31. Záporná čísla se nedají na kladná převést užitím absolutní hodnoty, je třeba přičíst násobek modulu N (a je rychlejší to udělat až s konečným výsledkem, viz postup výše).

Jinak u malých modulů bych se touto metodou vůbec netrápil a kongruence slučoval po dvou. Třeba u prvního příkladu: hledám číslo, které dává zbytek 3 po dělení 4 a 1 po dělení 3. Zkusím 3 - ne, zkusím 7, jo!, vím že dává bytek 7 po dělení 12. Teď ještě aby dávalo zbytek 1 po dělní 5. Zkusím 7, ne, zkusím 19, ne zkusím 31, bingo! Je jasné, že počet pokusů pro tři moduly je menší než součet nejmenšího a největšího modulu. A samozřejmě lze možnosti kombinovat, některá sloučení provést takto "z hlavy" a některá přes EGCD.

Technická k TeXu: $N:= \prod m_i = 60$ (součin se píše \prod).

Kedrigern · 09. 06. 2010 17:39

Děkuji moc, problém byl objasněn.

Ty produkty jsem opravil, hloupá chyba :).

Matematické Fórum

#1 09. 06. 2010 14:50 — Editoval Kedrigern (09. 06. 2010 16:19)

Modulární reprezentace čísla

#2 09. 06. 2010 16:05

Re: Modulární reprezentace čísla

#3 09. 06. 2010 17:39

Re: Modulární reprezentace čísla

Zápatí