szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 gru 2014, o 18:17 
Użytkownik

Posty: 1
Lokalizacja: nieiwem
Witam,

mam taki wzorek:

K  \cdot  2^{M} \pmod{N}
gdzie:
0 < K, M, N < 10^{9}
K < N
i N jest zawsze nieparzyste, interesuje mnie reszta z dzielenia tego, więc wydaje mi się, że wystarczy obliczyć 2^{M} \pmod{N} aby poznać wynik. Potrzebne jest mi to do zadania z programowania. Mam maksymalnie 100 operacji na obliczenie tego wzorku. Kompletnie nie interesują mnie wywody i udowodnienia, potrzebuję jakiegoś konkretnego algorytmu, albo zależności z której mogę to szybko policzyć. Proszę nie pisać zapisów czysto matematycznych, bo jestem dopiero w gimnazjum i nic z tego nie rozumiem :) Proszę o jakąś metodę na policzenie
2^{M} \pmod{N}

Pozdrawiam,
Ninjago
Góra
Mężczyzna Offline
PostNapisane: 8 gru 2014, o 19:52 
Użytkownik
Avatar użytkownika

Posty: 2909
Lokalizacja: Biała Podlaska / Warszawa
Poczytaj o szybkim potęgowaniu modularnym. Można to policzyć w czasie O(\log M)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Arytmetyka na liczbach naturalnych modulo p  Artut97  1
 Podzielność sumy przez 10 (potęgi).  ewa123  1
 Podzielność sumy liczb do potegi przez sume liczb do potęgi  MenosGrandes  8
 Przekształcenia, potęgi - zadanie 2  piootrek15  3
 Potęgi dwójki, podz. przez 6  patry93  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl