Matematické Fórum

↑ Pavel Brožek:

Tak ja napisu naznak toho, jak jsem uvazoval (neni to nic svetobornyho, spis takovy odrazovy mustek, ktery by snad mohl jit nejak vylepsit)

1. Nejprve zkusme zjistit, jak prijit na Fn modulo d, kde d je nejake prir. Cislo:
budu uvazovat dvijice po sobe jdoucich fib cisel modulo d, znacit to budu (A_k,B_k); zrejme pak plati (A_(k+1),B_(k+1))=(B_k,A_k+B_k mod d).
Ted: vsech moznych takovych dvojic je nejvyse d^2 a plati, ze kazda dvojice jednoznacne urcuje tu nasledujici. Tedy po nejvyse d^2 krocich se (teoreticky) vypocet zacykli a pak se opakuje periodicky nejaka posloupnost dvojic. Kdybychom znali delku pocatecniho useku ("pred prvni periodou"), ozn. P, a delku periody L, pak spocitame (A_n,B_n) jako (A_(n-P mod L), B_(n-P mod L)). Pritom dostat se ke dvojici takoveho indexu uz stoji "jen" (radove) L operaci, pritom L<d^2.

(Na tuto cast smerovaly oba dotazy - z druhe casti poplyne, ze by se hodilo d=p-1, a taky moci kodulit cislo n cislem L .. nikoli tedy cislo Fn, jen ten index)

No a druha vec je, ze pro x nesoudelne s p prvocislem plati x^(p-1) mod p =1 - tedy spec. Pro tvuj priklad je  2^(Fn) mod p =2^(Fn mod (p-1)) mod p. To jsou obecne vzato sice porad velka cisla, ale uz to nejsou aspon tak obludne velka cisla, ze by nevlezla do pameti apod.

Pozn: prinejmensim ta prvni cast bude urcite nejak vylepsit - bud dobrym odhadem (ktere dvojice muzou byt zmodulena dve po sobe jdouci fib cisla?) Nebo nejakym odvozenim explicitni formule fib cisla "modulo d".

Taky se omlouvam za neladnou formu, skrabu to na mobilu.

Tak jestli jsem něco nepřehlídl, tak už asi máme efektivní řešení. Jak jsi navrhl, tak z Malé Frematovy věty máme



Jakmile zjistíme exponent, tak už je jednoduché dopočítat zbytek.

už snadno spočítáme v rozumném čase pomocí postupu uvedeného tady (využívá toho, že je prvek jedné matice umocněné na n-tou, stačí tu matici mocnit modulo ). Počet mocnění bude zhruba , takže počet operací by měl být na běžném počítači snadno zvladatelný.

↑ OiBobik:

Jedna úloha z http://projecteuler.net/ vede právě na vyčíslování podobných výrazů. Bylo na tom hodně jiné práce než se člověk dostal k tomuhle, takže když vidíš to zadání, tak bys asi nejdřív vůbec netipnul, že to povede na takové věci :). Je to hrozně zajímavá úloha, bavilo mě ji řešit. Teď už mi zbývá jen implementovat ten algoritmus :)

Ahoj,
téma čtu až teď. Napadly mě dvě věci, ale asi budou časově náročnější. Vycházím z odkazu na wikipedii.
1) spočítat na základě dvou rekurentních vztahů v této kapitole zcela na jejím konci - časová složitost je O((log(n)) a v každém kroku bychom prováděli mod p-1.
2) Zvládneme-li faktorizaci p-1 na prvočísla, mohli bychom využít toto - a zkoumat pro q prvočíslo a využít předchozí odkaz a následně např. pomocí čínské zbytkové věty získat výsledek. To nám asi pomůže jen velmi málo - musíme se snažit při rekurentních vztazích získat .
Časové složitosti jsem detailně nepropočítával, ale asi to nebude nic moc.