Modulare Gleichung, Minimum?

29/04/2012 - 10:56 von Gottfried Helms | Report spam
Hi ,

ich untersuche die folgende diophantine Fragestellung.

Gegeben ein fester Wert B und damit 2^B .

Außerdem zwei Variable p,q, beide aus den Restklassen
(mod 2^B), also z.B. B=8, 2^B%6. p,q<%5

Ich nehme ein q als gegeben an, und wàhle p so, daß

pq-1
- + 1 = t und t integer
2^B

(d.h. p ist die modulare inverse p=1/q (mod 2^B ))
Beispiel q, ==> p7 weil pq-1*197-1%60 = 10*256

Meine erste Beobachtung war, daß unter diesen Bedingungen immer

pq-1
- + 1 <= min(p,q)
2^B

Das hatte ich dann gelöst. Aber die nàchste beobachtung war,
daß Gleichheit nur dann auftritt, wenn p (oder q) ein Teiler
von 2^B-1 ist, und sonst die "kleiner"-Beziehung gilt.

Beispiel: q ==> p7 q ist *kein* Teiler von 256-1
pq -1
256


Beispiel: q ==> p#9 q ist Teiler von 256-1
pq -1
256


Wie kann man das zeigen?

Gottfried
 

Lesen sie die antworten

#1 Jan Fricke
29/04/2012 - 21:51 | Warnen spam
On 04/29/2012 10:56 AM, Gottfried Helms wrote:
Hi ,

ich untersuche die folgende diophantine Fragestellung.

Gegeben ein fester Wert B und damit 2^B .

Außerdem zwei Variable p,q, beide aus den Restklassen
(mod 2^B), also z.B. B=8, 2^B%6. p,q<%5

Ich nehme ein q als gegeben an, und wàhle p so, daß

pq-1
- + 1 = t und t integer
2^B

(d.h. p ist die modulare inverse p=1/q (mod 2^B ))
Beispiel q, ==> p7 weil pq-1*197-1%60 = 10*256

Meine erste Beobachtung war, daß unter diesen Bedingungen immer

pq-1
- + 1<= min(p,q)
2^B

Das hatte ich dann gelöst. Aber die nàchste beobachtung war,
daß Gleichheit nur dann auftritt, wenn p (oder q) ein Teiler
von 2^B-1 ist, und sonst die "kleiner"-Beziehung gilt.

Beispiel: q ==> p7 q ist *kein* Teiler von 256-1
pq -1
256


Beispiel: q ==> p#9 q ist Teiler von 256-1
pq -1
256


Wie kann man das zeigen?



Stelle die Gleichung
(pq-1)/2^B + 1 = p

nach q um und Du erhàltst:

q = 2^B - (2^B - 1)/p.


Viele Grüße Jan

Ähnliche fragen