| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gost
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
 Postano: 12:47 sub, 21. 2. 2004 Naslov: |
    |
|
|
[quote="Anonymous"]*-množenje
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i)
a puta ( ... a puta 2 na i-1)[/quote]
Notation hints:
IMO, bolje je: ^ za potenciranje (standardni ASCII).
potenciranje ima veći prioritet od oduzimanja - dakle 2^(i-1) .
[quote]Neka je a neparan broj i x iz skupa {0,1}ˆ32. Zatim neka vrijedi slijedeće
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i), gdje 1<= i <=30.
Ono što me interesira je slijedeće:
1. Da li vrijedi
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i) => (x+a*2ˆi-1) = 0 (mod 2ˆ30-i) ? [/quote]
Da.
[quote]Zašto da ili ne ? [/quote]
Zato što to zapravo kaže da ako je a*nešto djeljivo s potencijom od 2 , tada je to nešto već djeljivo s potencijom od 2 - što postaje očito kad se shvati da je a neparan, i time relativno prost s bilo kojom potencijom od 2 . Općenito, ako k|m*n , a NZM(k,m)=1 , tada k|n (inače, ovo ima zanimljiv dokaz: ).
[quote]2. Da li vrijedi za 1<= i <=15 (u slučaju da je odgovor ne na 1.)
(x+a*2ˆi-1) = 0 (mod 2ˆ30-i) ?
Zašto da ili ne ? [/quote]
Budući da je odgovor na 1. "da", no comment. :-)
[quote]3. Da li vrijedi za 16<= i <=30
x = 0 (mod 2ˆ30-i) [/quote]
Da. Zato što za i u tim granicama vrijedi 30-i<=i-1 , odnosno 2^(30-i) dijeli 2^(i-1) (pa i a*2^(i-1) ). Budući da po uvjetu 2^(30-i) dijeli x+a*2^(i-1) , dijeli i njihovu razliku, odnosno x .
[quote]4. Zatim zašto iz 3. slijedi da najznačajniji bitovi (i-2) od x mogu poprimiti bilo koju vrijednost{0,1}?[/quote]
2^(30-i)|x znači da je zadnjih 30-i bitova od x jednako 0 , i znači točno to. Odnosno, preostali bitovi (točno njih i-2 s početka - jer ukupno ih ima 32 ) nemaju nikakvih uvjeta na sebe, pa mogu biti bilo kakvi.
| Anonymous (napisa): | *-množenje
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i)
a puta ( ... a puta 2 na i-1) |
Notation hints:
IMO, bolje je: ^ za potenciranje (standardni ASCII).
potenciranje ima veći prioritet od oduzimanja - dakle 2^(i-1) .
| Citat: | Neka je a neparan broj i x iz skupa {0,1}ˆ32. Zatim neka vrijedi slijedeće
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i), gdje 1⇐ i ⇐30.
Ono što me interesira je slijedeće:
1. Da li vrijedi
a*(x+a*2ˆi-1) = 0 (mod 2ˆ30-i) ⇒ (x+a*2ˆi-1) = 0 (mod 2ˆ30-i) ? |
Da.
Zato što to zapravo kaže da ako je a*nešto djeljivo s potencijom od 2 , tada je to nešto već djeljivo s potencijom od 2 - što postaje očito kad se shvati da je a neparan, i time relativno prost s bilo kojom potencijom od 2 . Općenito, ako k|m*n , a NZM(k,m)=1 , tada k|n (inače, ovo ima zanimljiv dokaz: ).
| Citat: | 2. Da li vrijedi za 1⇐ i ⇐15 (u slučaju da je odgovor ne na 1.)
(x+a*2ˆi-1) = 0 (mod 2ˆ30-i) ?
Zašto da ili ne ? |
Budući da je odgovor na 1. "da", no comment. 
| Citat: | 3. Da li vrijedi za 16⇐ i ⇐30
x = 0 (mod 2ˆ30-i) |
Da. Zato što za i u tim granicama vrijedi 30-i⇐i-1 , odnosno 2^(30-i) dijeli 2^(i-1) (pa i a*2^(i-1) ). Budući da po uvjetu 2^(30-i) dijeli x+a*2^(i-1) , dijeli i njihovu razliku, odnosno x .
| Citat: | | 4. Zatim zašto iz 3. slijedi da najznačajniji bitovi (i-2) od x mogu poprimiti bilo koju vrijednost{0,1}? |
2^(30-i)|x znači da je zadnjih 30-i bitova od x jednako 0 , i znači točno to. Odnosno, preostali bitovi (točno njih i-2 s početka - jer ukupno ih ima 32 ) nemaju nikakvih uvjeta na sebe, pa mogu biti bilo kakvi.
|
|
| [Vrh] |
|
Gost
|
| Postano: 17:51 uto, 24. 2. 2004 Naslov: |
|
|
|
[quote="veky"]Zato što to zapravo kaže da ako je a*nešto djeljivo s potencijom od 2 , tada je to nešto već djeljivo s potencijom od 2 - što postaje očito kad se shvati da je a neparan, i time relativno prost s bilo kojom potencijom od 2 . [b]Općenito, ako k|m*n , a NZM(k,m)=1 , tada k|n (inače, ovo ima zanimljiv dokaz: ). [/b][/quote]
Koliko sam skužil ovdje se ne može primjeniti općeniti slučaj tj.
3*6=0(mod2) NZM(3,6)=3. Općeniti slučaj bi bio neparan*x=paran => x paran ; neparan*paran= 0 (mod 2^i) => paran=0(mod 2^i) ili ...
| veky (napisa): | | Zato što to zapravo kaže da ako je a*nešto djeljivo s potencijom od 2 , tada je to nešto već djeljivo s potencijom od 2 - što postaje očito kad se shvati da je a neparan, i time relativno prost s bilo kojom potencijom od 2 . Općenito, ako k|m*n , a NZM(k,m)=1 , tada k|n (inače, ovo ima zanimljiv dokaz: ). |
Koliko sam skužil ovdje se ne može primjeniti općeniti slučaj tj.
3*6=0(mod2) NZM(3,6)=3. Općeniti slučaj bi bio neparan*x=paran ⇒ x paran ; neparan*paran= 0 (mod 2^i) ⇒ paran=0(mod 2^i) ili ...
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
@#
Forumaš(ica)
Pridružen/a: 28. 01. 2004. (19:08:55)
Postovi: (36)16
Lokacija: math
|
| Postano: 18:10 uto, 24. 2. 2004 Naslov: |
|
|
|
[quote="Anonymous"]:oops: bolji primjer za gore 9*18=0(mod2) NZM(9,18)=3.[/quote]
kolko ja vidim, to nema veze s ovim sto je napisano gore.. pise "ako k dijeli m puta n, a k i m su relativno prosti, onda k dijeli n". u zadatku je m neparan, a k je potencija od 2, pa su sigurno relativno prosti. nema veze sa nzmom od m i n..
| Anonymous (napisa): | | :oops: bolji primjer za gore 9*18=0(mod2) NZM(9,18)=3. |
kolko ja vidim, to nema veze s ovim sto je napisano gore.. pise "ako k dijeli m puta n, a k i m su relativno prosti, onda k dijeli n". u zadatku je m neparan, a k je potencija od 2, pa su sigurno relativno prosti. nema veze sa nzmom od m i n..
_________________
--
~#!'<0 !'0 0)' ('0|'# v|)'| =v# ...
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
|
=3.
