Mam do zrobienia program w języku c++, w którym definiujemy funkcję square(), która podnosi liczby do kwadratu. Utrudnienie jest takie, że w definiowanej funkcji nie mogę użyc operatora mnożenia.
Treść zadania jest taka:
zaimplementuj funkcję square(), nie uzywając operatora mnozenia. to znaczy operację x*x wykonaj za pomocą wielokrotnego dodawania (zacznij od zmiennej wartosci 0 i dodaj do niej
x x razy).
Zadanie to jest w ksiązce "Programowanie. Teoria i praktyka z wykorzystaniem C++." Bjarne Stroustrupa.
wszystko inne potrafię zrobić, jedynie nie wiem jak mogę zrobić funkcję podnoszącą liczbę do kwadratu nie używając mnożenia
- Rejestracja:ponad 4 lata
- Ostatnio:ponad 4 lata
- Postów:2
0
C++ 
- Rejestracja:ponad 4 lata
- Ostatnio:ponad 4 lata
- Postów:2
0
@kq: tak, ale jak sam napisałes: "b razy". a ja nie mogę w ogole uzywac mnozenia, czyli razy nie wchodzi w grę.
(chyba ze cos zle zrozumialam z twojej odpowiedzi, co bardzo mozliwe, jestem mocno początkująca)
AnyKtokolwiek
Materiał jest za zakresu 2 klasy podstawówki (tej dawnej stressowej szkoły, nie wiem, może teraz w ósmej?)
- Rejestracja:ponad 6 lat
- Ostatnio:około rok
- Postów:10
0
Testowane. Dziala
int mySquare (int podstawa,int wykladnik)
{
int wynik = podstawa, licznik1 = 0;
do
{
int licznik2 = 1;
if (licznik1 > 1)
{
int temp = wynik;
do
{
wynik+=temp;
licznik2++;
//cout << "Potega " << licznik1 << " " << wynik << endl;
}while(licznik2 < podstawa);
}
licznik1++;
}while(licznik1 <= wykladnik);
return wynik;
}
edytowany 1x, ostatnio: PG
- Rejestracja:prawie 12 lat
- Ostatnio:7 dni
- Postów:1027
3
A jak nie chcesz, żeby było aż tak wolno, to można mnożenie zrealizować tak:
int mult(int a, int b) {
int result = 0;
while (b > 0) {
if (b & 1) {
result += a;
}
a += a;
b >>= 1;
}
return result;
}
edytowany 1x, ostatnio: enedil
@Shalom: z całym szacunkiem, ale wersja gdzie pętla jest długości "wykładnika" to dużo poważniejszy side channel, bo bez analizy zużycia prądu masz dostęp do sporej części MSB wykładnika. No i chyba też wiesz, jak przerobić ten algorytm na nie leakujący informacji o
b.
E tam, niby co ci to daje? W przypadku RSA wiesz że wykładnik będzie miał tyle bitów co N, plus minus 1-2. Nie wiem jak to niby leakuje jakieś MSB. A co do przerabiania to wcale nie takie proste. Myślisz pewnie o
square and multiply always ale to wcale nie rozwiązuje problemu, bo nadal można to sidechannelować przez doubling attack. Patrz https://hack.cert.pl/challenge/wakacje_w_spa oraz https://hack.cert.pl/challenge/kolejne_wakacje_w_spa :P
Hmm? Mówiłem o algorytmie potęgowania przez iterację
wykładnik razy (porównanie do algorytmu proponowanego przez kq), w zależności od precyzji momiaru można dostać długość pętli. W przypadku RSA to daje jakieś info n.t. klucza prywatnego jeśli umiesz rozróżniać czasy obliczeń różniące się o mniej niż sqrt(N) obrotów pętli. A co do zmiany algorytmu, to racja, myślałem o square and multiply always. Przeczytam o tych atakach, dzięki za hinta