Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
ignore 04494.08 - Curve25519
13 views
Skip to first unread message
Marcel Logen
Mar 29, 2023, 8:31:46 PM3/29/23
to
ignore 04494.08 - Curve25519
<https://ybtra.de/div/2023h1/20230330a.png>,
besser mit offizieller Korrektur:
<https://ybtra.de/div/2023h1/20230330d.png>
<https://ybtra.de/div/2023h1/20230330b.png>
<https://ybtra.de/div/2023h1/20230330c.png>
Mal sehen, ob ich da (einigermaßen) durchsteige ...
Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
davon zu verifizieren bzw. zu verstehen.
Vieles bleibt jedoch offen.
Marcel 2oh45 (2901125)
--
╭─╮ ╭─────╮ ╭──────╮ ╭─╮
╭───╯ │ ╭──╯ ╭──╯ ╭─╮ ╰───╮ ╰─╮ ╭──╯ ╰───
╭──╮ ╭──╮ ╭─╯ ╭─╯ ╰─╮ │ ╭─╮ │ │ ╭────╯ ╭─╯ ╭─╮ │
─╯ ╰──╯ ╰─╯ ╰──────╯ ╰─╯ ╰─╯ ╰─╯ ╰─────╯ ╰───────╯ 863db4
<https://ybtra.de/div/2023h1/20230330a.png>,
besser mit offizieller Korrektur:
<https://ybtra.de/div/2023h1/20230330d.png>
<https://ybtra.de/div/2023h1/20230330b.png>
<https://ybtra.de/div/2023h1/20230330c.png>
Mal sehen, ob ich da (einigermaßen) durchsteige ...
Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
davon zu verifizieren bzw. zu verstehen.
Vieles bleibt jedoch offen.
Marcel 2oh45 (2901125)
--
╭─╮ ╭─────╮ ╭──────╮ ╭─╮
╭───╯ │ ╭──╯ ╭──╯ ╭─╮ ╰───╮ ╰─╮ ╭──╯ ╰───
╭──╮ ╭──╮ ╭─╯ ╭─╯ ╰─╮ │ ╭─╮ │ │ ╭────╯ ╭─╯ ╭─╮ │
─╯ ╰──╯ ╰─╯ ╰──────╯ ╰─╯ ╰─╯ ╰─╯ ╰─────╯ ╰───────╯ 863db4
Christian Schumacher
Mar 30, 2023, 2:37:42 AM3/30/23
to
Marcel Logen schrieb am Do, 30 Mär 2023 02:31:
> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>
> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
> davon zu verifizieren bzw. zu verstehen.
🚂
> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>
> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
> davon zu verifizieren bzw. zu verstehen.
--
Gruß
Christian
»Der Stress von heute ist die gute alte Zeit von übermorgen.«
Marcel Logen
Mar 30, 2023, 3:49:52 PM3/30/23
to
Christian Schumacher in de.test:
>Marcel Logen schrieb am Do, 30 Mär 2023 02:31:
>> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>
>> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>> davon zu verifizieren bzw. zu verstehen.
>
>🚂
Hm, "U+1F682 STEAM LOCOMOTIVE".
Meintest Du vielleicht "U+1F689 STATION"? :-)
🚉
Marcel
--
╭──────╮ ╭────╮ ╭───╮ ╭─╮ ╭──╮ ╭─╮ ..67..
╰────╮ ╰─╯ ╰─╯ │ ╭──╯ ╰──╮ │ │ │ ╰──╮ ╭──╮..67..
─╮ ╭────╮ │ ╭─────────╯ │ ╭───╯ ╭─╯ ╰───╯ ╰───╯ ╰──╮
╰───╯ ╰──╯ ╰────────────╯ ╰────────╯ ..63..╰───
>Marcel Logen schrieb am Do, 30 Mär 2023 02:31:
>> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>
>> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>> davon zu verifizieren bzw. zu verstehen.
>
>🚂
Meintest Du vielleicht "U+1F689 STATION"? :-)
🚉
Marcel
--
╭──────╮ ╭────╮ ╭───╮ ╭─╮ ╭──╮ ╭─╮ ..67..
╰────╮ ╰─╯ ╰─╯ │ ╭──╯ ╰──╮ │ │ │ ╰──╮ ╭──╮..67..
─╮ ╭────╮ │ ╭─────────╯ │ ╭───╯ ╭─╯ ╰───╯ ╰───╯ ╰──╮
╰───╯ ╰──╯ ╰────────────╯ ╰────────╯ ..63..╰───
Marcel Logen
Mar 31, 2023, 11:58:17 AM3/31/23
to
Marcel Logen in de.test:
><https://ybtra.de/div/2023h1/20230330a.png>,
>besser mit offizieller Korrektur:
><https://ybtra.de/div/2023h1/20230330d.png>
>
><https://ybtra.de/div/2023h1/20230330b.png>
>
><https://ybtra.de/div/2023h1/20230330c.png>
>
>Mal sehen, ob ich da (einigermaßen) durchsteige ...
>
>Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>davon zu verifizieren bzw. zu verstehen.
<https://ybtra.de/div/2023h1/20230330c.png>
Dort ist von einem "l = 2^252 + 277432...648493" die Rede,
das scheint der "order" aus
<https://ybtra.de/div/2023h1/20230330a.png> zu entsprechen:
| user15@o15:/tmp$ echo '14def9dea2f79cd65812631a5cf5d3ed' | tr 'a-f' 'A-F'
| 14DEF9DEA2F79CD65812631A5CF5D3ED
| user15@o15:/tmp$ bc -lq
| ibase=16
| 14DEF9DEA2F79CD65812631A5CF5D3ED
| 27742317777372353535851937790883648493
| user15@o15:/tmp$
Dann gibt es dort (in "...c.png") noch den Wert
"-121665/121666". Das ist schon interessanter!
Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
aller natürlichen Zahlen kleiner 2^255-19.
Das ist jetzt Modulo-Rechnung angesagt.
Zunächst mal das additive Inverse ("minus") von 121665
berechnen (modulo 2^255-19):
| user15@o15:/tmp$ bc -lq
| scale=0
| (-121665+2^255-19) % (2^255-19)
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564698284
Dann das multiplikative Inverse ("geteilt durch") von
121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
terten euklidischen Algorithmus:
(Ich muß hier leider unterbrechen. Später geht's weiter.)
>Vieles bleibt jedoch offen.
Viel zu Vieles.
Marcel
--
╭─────╮ ╭──╮ ..34..╭─────────────╮ ╭──╮ ╭──╮ ╭─╮
╰─╮ │ ╭──────╯ ╰─╮ ╰──────╮..48..╰──╯ ╰─╯ ╰─╯ ╰───
───╯ │ ╰──╮ ╰─╮ ╭─────╮ ╭───╮ │ ..67..
╰───────╯ ╰─╯ ╰─────╯ ╰─╯ ..67..
><https://ybtra.de/div/2023h1/20230330a.png>,
>besser mit offizieller Korrektur:
><https://ybtra.de/div/2023h1/20230330d.png>
>
><https://ybtra.de/div/2023h1/20230330b.png>
>
><https://ybtra.de/div/2023h1/20230330c.png>
>
>Mal sehen, ob ich da (einigermaßen) durchsteige ...
>
>Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>davon zu verifizieren bzw. zu verstehen.
Dort ist von einem "l = 2^252 + 277432...648493" die Rede,
das scheint der "order" aus
<https://ybtra.de/div/2023h1/20230330a.png> zu entsprechen:
| user15@o15:/tmp$ echo '14def9dea2f79cd65812631a5cf5d3ed' | tr 'a-f' 'A-F'
| 14DEF9DEA2F79CD65812631A5CF5D3ED
| user15@o15:/tmp$ bc -lq
| ibase=16
| 14DEF9DEA2F79CD65812631A5CF5D3ED
| 27742317777372353535851937790883648493
| user15@o15:/tmp$
Dann gibt es dort (in "...c.png") noch den Wert
"-121665/121666". Das ist schon interessanter!
Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
aller natürlichen Zahlen kleiner 2^255-19.
Das ist jetzt Modulo-Rechnung angesagt.
Zunächst mal das additive Inverse ("minus") von 121665
berechnen (modulo 2^255-19):
| user15@o15:/tmp$ bc -lq
| scale=0
| (-121665+2^255-19) % (2^255-19)
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564698284
Dann das multiplikative Inverse ("geteilt durch") von
121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
terten euklidischen Algorithmus:
(Ich muß hier leider unterbrechen. Später geht's weiter.)
>Vieles bleibt jedoch offen.
Viel zu Vieles.
Marcel
--
╭─────╮ ╭──╮ ..34..╭─────────────╮ ╭──╮ ╭──╮ ╭─╮
╰─╮ │ ╭──────╯ ╰─╮ ╰──────╮..48..╰──╯ ╰─╯ ╰─╯ ╰───
───╯ │ ╰──╮ ╰─╮ ╭─────╮ ╭───╮ │ ..67..
╰───────╯ ╰─╯ ╰─────╯ ╰─╯ ..67..
Marcel Logen
Mar 31, 2023, 3:13:29 PM3/31/23
to
Marcel Logen in de.test:
>>Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>
>>Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>>davon zu verifizieren bzw. zu verstehen.
>
><https://ybtra.de/div/2023h1/20230330c.png>
[...]
>Dann gibt es dort (in "...c.png") noch den Wert
>"-121665/121666". Das ist schon interessanter!
>
>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>aller natürlichen Zahlen kleiner 2^255-19.
>
>Das ist jetzt Modulo-Rechnung angesagt.
>
>Zunächst mal das additive Inverse ("minus") von 121665
>berechnen (modulo 2^255-19):
>
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| (-121665+2^255-19) % (2^255-19)
>| 57896044618658097711785492504343953926634992332820282019728792003956\
>| 564698284
>
>Dann das multiplikative Inverse ("geteilt durch") von
>121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
>terten euklidischen Algorithmus:
>
>(Ich muß hier leider unterbrechen. Später geht's weiter.)
Außerdem lief mein unter dem OpenBSD-bc erstelltes Tool
für den erweiterten euklidischen Algorithmus (EEA) leider
nicht hier mit dem Linux(GNU)-bc, so daß ich da erst noch
einige Änderungen durchführen mußte.
<https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus>
Also: Berechnung von 1/121666 mod (2^255-19).
BTW: 2^255-19 = 57896044618658097711785492504343953926634992332820282019728792003956564819949
| user15@o15:/tmp$ bc -q bc-eea
|
| ggT(121666,578960446186580977117854925043439539266349923328202820197\
| 28792003956564819949)=1
| i=17
| a[i]=1
| b[i]=0
|
| a[0]=121666
| b[0]=578960446186580977117854925043439539266349923328202820197287920\
| 03956564819949
| s[0]=-20800338683988658368647408995589388737092878452977063003340006\
| 470870624536393
| t[0]=43711
| a[0]*s[0]+b[0]*t[0]=1
D. h.: s[0] + 2^255 -19 sollte das multiplikative Inverse
von 121666 sein:
| user15@o15:/tmp$ bc -q
| scale=0
| s[0]=-20800338683988658368647408995589388737092878452977063003340006470870624536393
| minv=(s[0]+2^255-19)
| minv
| 37095705934669439343138083508754565189542113879843219016388785533085\
| 940283556
| ainv=57896044618658097711785492504343953926634992332820282019728792003956564698284
| ainv*minv
| 21476946459542418524840405674862671881784022704458929071401217931577\
| 64109873057167859953089640989243313166333252467162351931143254652701\
| 769450186546617904
| ergebnis=(ainv*minv)%(2^255-19)
| ergebnis
| 37095705934669439343138083508754565189542113879843219016388785533085\
| 940283555
| minv-ergebnis
| 1
Erstaunlich finde ich BTW die letzten beiden Zeilen.
Jedenfalls stimmt das "ergebnis", also
(-121665/121666)mod(2^255-19), mit dem Wert d aus
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
überein.
d = 37095705934669439343138083508754565189542113879843219016388785533085940283555
Ich hoffe, ich habe mich bei dem Ganzen nicht vertan. :-)
Marcel
--
╭─╮ ╭─╮ ╭─╮ ..50..╭─╮ ╭───────────
╭──╮ ╭──╯ ╰─╯ │ ╭───╮ ╭───╮ │ ╰───╮..50..│ │ ╰────────╮
│ │ ╰─────╮ │ ╭──╮ ╭─╯ ╰───╯ ╰──╯ ╰──────╯ │ ╭────────╯
╯ ╰────────╯ ╰───╯ ╰──╯ ╰──╯ ..67..
>>Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>
>>Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>>davon zu verifizieren bzw. zu verstehen.
>
><https://ybtra.de/div/2023h1/20230330c.png>
>Dann gibt es dort (in "...c.png") noch den Wert
>"-121665/121666". Das ist schon interessanter!
>
>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>aller natürlichen Zahlen kleiner 2^255-19.
>
>Das ist jetzt Modulo-Rechnung angesagt.
>
>Zunächst mal das additive Inverse ("minus") von 121665
>berechnen (modulo 2^255-19):
>
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| (-121665+2^255-19) % (2^255-19)
>| 57896044618658097711785492504343953926634992332820282019728792003956\
>| 564698284
>
>Dann das multiplikative Inverse ("geteilt durch") von
>121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
>terten euklidischen Algorithmus:
>
>(Ich muß hier leider unterbrechen. Später geht's weiter.)
für den erweiterten euklidischen Algorithmus (EEA) leider
nicht hier mit dem Linux(GNU)-bc, so daß ich da erst noch
einige Änderungen durchführen mußte.
<https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus>
Also: Berechnung von 1/121666 mod (2^255-19).
BTW: 2^255-19 = 57896044618658097711785492504343953926634992332820282019728792003956564819949
| user15@o15:/tmp$ bc -q bc-eea
|
| ggT(121666,578960446186580977117854925043439539266349923328202820197\
| 28792003956564819949)=1
| i=17
| a[i]=1
| b[i]=0
|
| a[0]=121666
| b[0]=578960446186580977117854925043439539266349923328202820197287920\
| 03956564819949
| s[0]=-20800338683988658368647408995589388737092878452977063003340006\
| 470870624536393
| t[0]=43711
| a[0]*s[0]+b[0]*t[0]=1
D. h.: s[0] + 2^255 -19 sollte das multiplikative Inverse
von 121666 sein:
| user15@o15:/tmp$ bc -q
| scale=0
| s[0]=-20800338683988658368647408995589388737092878452977063003340006470870624536393
| minv=(s[0]+2^255-19)
| minv
| 37095705934669439343138083508754565189542113879843219016388785533085\
| 940283556
| ainv=57896044618658097711785492504343953926634992332820282019728792003956564698284
| ainv*minv
| 21476946459542418524840405674862671881784022704458929071401217931577\
| 64109873057167859953089640989243313166333252467162351931143254652701\
| 769450186546617904
| ergebnis=(ainv*minv)%(2^255-19)
| ergebnis
| 37095705934669439343138083508754565189542113879843219016388785533085\
| 940283555
| minv-ergebnis
| 1
Erstaunlich finde ich BTW die letzten beiden Zeilen.
Jedenfalls stimmt das "ergebnis", also
(-121665/121666)mod(2^255-19), mit dem Wert d aus
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
überein.
d = 37095705934669439343138083508754565189542113879843219016388785533085940283555
Ich hoffe, ich habe mich bei dem Ganzen nicht vertan. :-)
Marcel
--
╭─╮ ╭─╮ ╭─╮ ..50..╭─╮ ╭───────────
╭──╮ ╭──╯ ╰─╯ │ ╭───╮ ╭───╮ │ ╰───╮..50..│ │ ╰────────╮
│ │ ╰─────╮ │ ╭──╮ ╭─╯ ╰───╯ ╰──╯ ╰──────╯ │ ╭────────╯
╯ ╰────────╯ ╰───╯ ╰──╯ ╰──╯ ..67..
Marcel Logen
Mar 31, 2023, 6:24:09 PM3/31/23
to
Marcel Logen in de.test:
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>[...]
>
>>Dann gibt es dort (in "...c.png") noch den Wert
>>"-121665/121666". Das ist schon interessanter!
>>
>>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>>aller natürlichen Zahlen kleiner 2^255-19.
>>
>>Das ist jetzt Modulo-Rechnung angesagt.
>>
>>Zunächst mal das additive Inverse ("minus") von 121665
>>berechnen (modulo 2^255-19):
[...]
>>Dann das multiplikative Inverse ("geteilt durch") von
>>121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
>>terten euklidischen Algorithmus:
[...]
>Also: Berechnung von 1/121666 mod (2^255-19).
[...]
>D. h.: s[0] + 2^255 -19 sollte das multiplikative Inverse
>von 121666 sein:
>
>| user15@o15:/tmp$ bc -q
>| scale=0
>| s[0]=-20800338683988658368647408995589388737092878452977063003340006470870624536393
>| minv=(s[0]+2^255-19)
>| minv
>| 37095705934669439343138083508754565189542113879843219016388785533085\
>| 940283556
>| ainv=57896044618658097711785492504343953926634992332820282019728792003956564698284
>| ainv*minv
>| 21476946459542418524840405674862671881784022704458929071401217931577\
>| 64109873057167859953089640989243313166333252467162351931143254652701\
>| 769450186546617904
>| ergebnis=(ainv*minv)%(2^255-19)
>| ergebnis
>| 37095705934669439343138083508754565189542113879843219016388785533085\
>| 940283555
>| minv-ergebnis
>| 1
>
>Erstaunlich finde ich BTW die letzten beiden Zeilen.
Inzwischen habe ich bemerkt, daß das wohl doch nicht ganz
so erstaunlich ist, denn
minv = minv(121666)
ainv = ainv(121665)
und
minv - ergebnis = (minv(121666) - (ainv(121665)*minv(121666))) % (2^255-19)
oder
= (1/121666 - (-121665)/121666) % (2^255-19)
= (121666/121666) % (2^255-19)
Tja. Ob man da in der Menge Fq ("field"?) mit q = 2^255-19
einfach so addieren, subtrahieren, multiplizieren und divi-
dieren kann?
<https://en.wikipedia.org/wiki/Field_(mathematics)>
<https://en.wikipedia.org/wiki/Field_(mathematics)#Finite_fields>
Vermutlich ja, da q eine Primzahl ist.
| user15@o15:/tmp$ openssl prime $(echo '2^255-19' | bc -ql | tr -d '\012\\') | tr ' ' '\012'
| 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED
| (57896044618658097711785492504343953926634992332820282019728792003956564819949)
| is
| prime
| user15@o15:/tmp$
Marcel
--
╭────╮ ╭────────╮ ╭─╮ ╭──────╮ ╭─╮ ..58..╭───╮ ╭─
╭─╯ ╭─╯ ╰──────╮ ╰─╯ │ ╭───╯ ╭───╯ ╭─╯ │ ..58..│ ╰──╯
──╮ ╰─╮ ╰──────╮ ╭─╯ │ ╭─╯ ╭───╯ ╭─╮ ╰─╮ ╰────╮ │ ..67..
╰────╯ ╰──╯ ╰────╯ ╰──────╯ ╰────╯ ╰───╯ ..67..
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>[...]
>
>>Dann gibt es dort (in "...c.png") noch den Wert
>>"-121665/121666". Das ist schon interessanter!
>>
>>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>>aller natürlichen Zahlen kleiner 2^255-19.
>>
>>Das ist jetzt Modulo-Rechnung angesagt.
>>
>>Zunächst mal das additive Inverse ("minus") von 121665
>>berechnen (modulo 2^255-19):
>>Dann das multiplikative Inverse ("geteilt durch") von
>>121666 (modulo 2^255-19), und zwar mit Hilfe des erwei-
>>terten euklidischen Algorithmus:
>Also: Berechnung von 1/121666 mod (2^255-19).
>D. h.: s[0] + 2^255 -19 sollte das multiplikative Inverse
>von 121666 sein:
>
>| user15@o15:/tmp$ bc -q
>| scale=0
>| s[0]=-20800338683988658368647408995589388737092878452977063003340006470870624536393
>| minv=(s[0]+2^255-19)
>| minv
>| 37095705934669439343138083508754565189542113879843219016388785533085\
>| 940283556
>| ainv=57896044618658097711785492504343953926634992332820282019728792003956564698284
>| ainv*minv
>| 21476946459542418524840405674862671881784022704458929071401217931577\
>| 64109873057167859953089640989243313166333252467162351931143254652701\
>| 769450186546617904
>| ergebnis=(ainv*minv)%(2^255-19)
>| ergebnis
>| 37095705934669439343138083508754565189542113879843219016388785533085\
>| 940283555
>| minv-ergebnis
>| 1
>
>Erstaunlich finde ich BTW die letzten beiden Zeilen.
so erstaunlich ist, denn
minv = minv(121666)
ainv = ainv(121665)
und
minv - ergebnis = (minv(121666) - (ainv(121665)*minv(121666))) % (2^255-19)
oder
= (1/121666 - (-121665)/121666) % (2^255-19)
= (121666/121666) % (2^255-19)
Tja. Ob man da in der Menge Fq ("field"?) mit q = 2^255-19
einfach so addieren, subtrahieren, multiplizieren und divi-
dieren kann?
<https://en.wikipedia.org/wiki/Field_(mathematics)>
<https://en.wikipedia.org/wiki/Field_(mathematics)#Finite_fields>
Vermutlich ja, da q eine Primzahl ist.
| user15@o15:/tmp$ openssl prime $(echo '2^255-19' | bc -ql | tr -d '\012\\') | tr ' ' '\012'
| 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED
| (57896044618658097711785492504343953926634992332820282019728792003956564819949)
| is
| prime
| user15@o15:/tmp$
Marcel
--
╭────╮ ╭────────╮ ╭─╮ ╭──────╮ ╭─╮ ..58..╭───╮ ╭─
╭─╯ ╭─╯ ╰──────╮ ╰─╯ │ ╭───╯ ╭───╯ ╭─╯ │ ..58..│ ╰──╯
──╮ ╰─╮ ╰──────╮ ╭─╯ │ ╭─╯ ╭───╯ ╭─╮ ╰─╮ ╰────╮ │ ..67..
╰────╯ ╰──╯ ╰────╯ ╰──────╯ ╰────╯ ╰───╯ ..67..
Marcel Logen
Mar 31, 2023, 6:43:00 PM3/31/23
to
Marcel Logen in de.test:
[...]
> = (1/121666 - (-121665)/121666) % (2^255-19)
> = (121666/121666) % (2^255-19)
>
>Tja. Ob man da in der Menge Fq ("field"?) mit q = 2^255-19
>einfach so addieren, subtrahieren, multiplizieren und divi-
>dieren kann?
>
><https://en.wikipedia.org/wiki/Field_(mathematics)>
><https://en.wikipedia.org/wiki/Field_(mathematics)#Finite_fields>
>
>Vermutlich ja, da q eine Primzahl ist.
Hm, das deutsche mathematische Fachwort für "field" ist
wohl "Körper". Dann paßt das natürlich auch mit der Addi-
tion und der Multiplikation.
<https://de.wikipedia.org/wiki/K%C3%B6rper_(Algebra)>
<https://de.wikipedia.org/wiki/K%C3%B6rper_(Algebra)#Endliche_K%C3%B6rper>
Marcel
--
╰─╮ ╭─╮ ╭───────╮ ╭──╮ ╭──────╮ ..59..╭──╮
│ ╭─╮ ╭─╮ │ ╰─╮ ╭──╮ │ ╭───╯ │ │ ╰──╮ │ ╭─╮ │ │
╰──╯ ╰─╮ │ │ │ │ │ ╰──╯ ╰──────╯ │ ╭──╯ ╰─╯ ╰─────╯ ╰──╮
╰─╯ ╰──╯ ╰───╯ ╰──╯ ..65..╰─
[...]
> = (1/121666 - (-121665)/121666) % (2^255-19)
> = (121666/121666) % (2^255-19)
>
>Tja. Ob man da in der Menge Fq ("field"?) mit q = 2^255-19
>einfach so addieren, subtrahieren, multiplizieren und divi-
>dieren kann?
>
><https://en.wikipedia.org/wiki/Field_(mathematics)>
><https://en.wikipedia.org/wiki/Field_(mathematics)#Finite_fields>
>
>Vermutlich ja, da q eine Primzahl ist.
wohl "Körper". Dann paßt das natürlich auch mit der Addi-
tion und der Multiplikation.
<https://de.wikipedia.org/wiki/K%C3%B6rper_(Algebra)>
<https://de.wikipedia.org/wiki/K%C3%B6rper_(Algebra)#Endliche_K%C3%B6rper>
Marcel
--
╰─╮ ╭─╮ ╭───────╮ ╭──╮ ╭──────╮ ..59..╭──╮
│ ╭─╮ ╭─╮ │ ╰─╮ ╭──╮ │ ╭───╯ │ │ ╰──╮ │ ╭─╮ │ │
╰──╯ ╰─╮ │ │ │ │ │ ╰──╯ ╰──────╯ │ ╭──╯ ╰─╯ ╰─────╯ ╰──╮
╰─╯ ╰──╯ ╰───╯ ╰──╯ ..65..╰─
Christian Schumacher
Apr 1, 2023, 5:07:45 AM4/1/23
to
Marcel Logen schrieb am Do, 30 Mär 2023 21:49:
> Christian Schumacher in de.test:
>
>>Marcel Logen schrieb am Do, 30 Mär 2023 02:31:
>
>>> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>>
>>> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>>> davon zu verifizieren bzw. zu verstehen.
>>
>>🚂
>
> Hm, "U+1F682 STEAM LOCOMOTIVE".
>
> Meintest Du vielleicht "U+1F689 STATION"? :-)
> 🚉
Ja, "Bahnhof" halt. Aber die Symbolik bei "Station" fand ich schwieriger
> Christian Schumacher in de.test:
>
>>Marcel Logen schrieb am Do, 30 Mär 2023 02:31:
>
>>> Mal sehen, ob ich da (einigermaßen) durchsteige ...
>>>
>>> Ein paar Berechnungen habe ich schon angestellt, um manche Dinge
>>> davon zu verifizieren bzw. zu verstehen.
>>
>>🚂
>
> Hm, "U+1F682 STEAM LOCOMOTIVE".
>
> Meintest Du vielleicht "U+1F689 STATION"? :-)
> 🚉
zu erkennen als bei der Dampflok.
--
Gruß
Christian
»Internet macht den Hintern fett.«
Marcel Logen
Apr 1, 2023, 6:13:36 AM4/1/23
to
Christian Schumacher in de.test:
>Ja, "Bahnhof" halt. Aber die Symbolik bei "Station" fand ich schwieriger
>zu erkennen als bei der Dampflok.
Das stimmt. Insbesondere hier
<https://www.unicode.org/charts/PDF/U1F680.pdf>
kann man da IMHO nicht gerade einen Bahnhof erkennen.
Hier
<https://www.fileformat.info/info/unicode/char/1f689/browsertest.htm>
sieht es schon deutlich besser aus (selbst in der s/w-Version).
Marcel
--
│ ╭───────╮ ╭───────╮ ╭──╮ ..67..
╰──╮ ╰─╮ ╰──╮ │ ╭───╯ ╭──╯ │ ..64..╭──
╭─╯ ╭───────────╯ ..25..╰───╮ ╰─╮ │ ╭──╮ ╰──╮ ╰───╮ ╭─╯
╰───────╯ ╰────╯ ╰──╯ ╰────────╯..58..╰───╯
>Ja, "Bahnhof" halt. Aber die Symbolik bei "Station" fand ich schwieriger
>zu erkennen als bei der Dampflok.
<https://www.unicode.org/charts/PDF/U1F680.pdf>
kann man da IMHO nicht gerade einen Bahnhof erkennen.
Hier
<https://www.fileformat.info/info/unicode/char/1f689/browsertest.htm>
sieht es schon deutlich besser aus (selbst in der s/w-Version).
Marcel
--
│ ╭───────╮ ╭───────╮ ╭──╮ ..67..
╰──╮ ╰─╮ ╰──╮ │ ╭───╯ ╭──╯ │ ..64..╭──
╭─╯ ╭───────────╯ ..25..╰───╮ ╰─╮ │ ╭──╮ ╰──╮ ╰───╮ ╭─╯
╰───────╯ ╰────╯ ╰──╯ ╰────────╯..58..╰───╯
Marcel Logen
Apr 1, 2023, 6:31:24 AM4/1/23
to
Marcel Logen in de.test:
>>><https://ybtra.de/div/2023h1/20230330c.png>
[...]
>>>Dann gibt es dort (in "...c.png") noch den Wert
>>>"-121665/121666". Das ist schon interessanter!
>>>
>>>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>>>aller natürlichen Zahlen kleiner 2^255-19.
Jetzt mal die "4/5" aus dem c-Bild. Das soll ja eine
>>><https://ybtra.de/div/2023h1/20230330c.png>
[...]
>>>Dann gibt es dort (in "...c.png") noch den Wert
>>>"-121665/121666". Das ist schon interessanter!
>>>
>>>Das ist wohl ein Wert aus Fq = {0,1,2,3,...,2^255-20}, also
>>>aller natürlichen Zahlen kleiner 2^255-19.
y-Koordinate auf der elliptischen Kurve E sein, aber
vielleicht komme ich da ja mit einer Modulo-Berechnung
auch weiter.
Zunächst noch mal der Wert von 2^255-19:
| user15@o15:/tmp$ echo '2^255-19' | bc -lq | tr -d '\\\012' ; echo
| 57896044618658097711785492504343953926634992332820282019728792003956564819949
| user15@o15:/tmp$
Dann das multiplikative Inverse von 5 (mod 2^255-19)
ausrechnen (erw. euklid. Algo.):
| user15@o15:/tmp$ bc -q bc-eea | tr '\012' '~' | sed -e 's/\\~//g' | tr '~' '\012'
|
| ggT(5,57896044618658097711785492504343953926634992332820282019728792003956564819949)=1
| i=4
| a[i]=1
| b[i]=0
|
| a[0]=5
| b[i]=0
|
| b[0]=57896044618658097711785492504343953926634992332820282019728792003956564819949
| s[0]=11579208923731619542357098500868790785326998466564056403945758400791312963990
| t[0]=-1
| a[0]*s[0]+b[0]*t[0]=1
s[0] ist das Inverse von 5.
| user15@o15:/tmp$ bc -lq
| scale=0
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819950
| 5 * 11579208923731619542357098500868790785326998466564056403945758400791312963990 - (2^255-19)
| 1
| (5 * 11579208923731619542357098500868790785326998466564056403945758400791312963990 ) % (2^255-19)
| 1
Das war die Kontrolle (ob auch das multiplikative neutrale
Element 1 dabei herauskommt).
| (4 * 11579208923731619542357098500868790785326998466564056403945758400791312963990 ) % (2^255-19)
| 46316835694926478169428394003475163141307993866256225615783033603165\
| 251855960
Und das ist der Wert "4/5 mod (2^255-19)".
Man vergleiche mit Y(P) aus
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>!
:-)
Marcel
--
╭─╮ ╭────╮ ╭──╮ ╭────╮ ╭──────╮ ╭────────╮ ..67..
─╯ ╰──────╮ ╰─╮ ╰─╯ ╰─╮ ╰──╮ ╰─╯ ╭───╯ ╰───╮ ╭─╯ ..59..╭───────
╭──╯ ╭──╯ ╭─╯ ╭──╮ ╰─╮ ╭─╯ ╭─╮ ╭──╯ │ ╭─╮ │ ..67..
╰────╯ ╰───╯ ╰────╯ ╰────╯ ╰──╯ ╰───╯ ╰───╯ ..67..
Marcel Logen
Apr 1, 2023, 12:28:20 PM4/1/23
to
>Jetzt mal die "4/5" aus dem c-Bild. Das soll ja eine
>y-Koordinate auf der elliptischen Kurve E sein, aber
>vielleicht komme ich da ja mit einer Modulo-Berechnung
>auch weiter.
[...]
>y-Koordinate auf der elliptischen Kurve E sein, aber
>vielleicht komme ich da ja mit einer Modulo-Berechnung
>auch weiter.
>| (4 * 11579208923731619542357098500868790785326998466564056403945758400791312963990 ) % (2^255-19)
>| 46316835694926478169428394003475163141307993866256225615783033603165\
>| 251855960
>
>Und das ist der Wert "4/5 mod (2^255-19)".
>
>Man vergleiche mit Y(P) aus
><https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>!
>:-)
alle durch. Es geht weiter (oder auch nicht ;-) mit der
Quadratwurzel aus 486664 (mod 2^255-19 natürlich).
<https://de.wikipedia.org/wiki/Quadratwurzel#Quadratwurzeln_modulo_n>
Das scheint mir eine schwierige Sache zu sein.
Fängt schon bei den Legendre-Symbolen an, die einen sehr
großen Exponenten haben. Da macht bc - der "arbitrary pre-
cision calculator" - dann leider die Grätsche.
| user15@o15:/tmp$ bc -lq
| scale=0
| Runtime error (func=(main), adr=27): exponent too large in raise
| user15@o15:/tmp$ echo 'limits' | bc
| BC_BASE_MAX = 2147483647
| BC_DIM_MAX = 16777215
| BC_SCALE_MAX = 2147483647
| BC_STRING_MAX = 2147483647
| MAX Exponent = 9223372036854775807
| Number of vars = 32767
| user15@o15:/tmp$
In
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
ist BTW die Rede von "sqrt(-486664)".
Ich habe mit den Angaben aus Section 4.1 den Wurzel-Wert
berechnen können, aber das kann es ja eigentlich nicht
sein ...
Marcel
--
╰───╮ ╭───╮ ╭──────────╮ ..36..╭─────────╮ ╭───────╮ ╭─
╭──╯ ╭─╯ ╰─╮ ╰────╮ ╭──╯ ╭─╮ │ ..46..╰─╮ ╰──╮ ╭─╯ ╭─╯
╰───╮ │ ╭────╯ ╭──╮ ╭─╯ ╰────╮ ╭─╯ │ │ ..45..╭──╯ ╭──╯ │ ╰──╮
╰─╯ ╰──────╯ ╰─╯ ╰──╯ ╰─╯ ..45..╰──────╯ ╰───────╯
Marcel Logen
Apr 1, 2023, 3:46:08 PM4/1/23
to
Marcel Logen in de.test:
[<https://ybtra.de/div/2023h1/20230330c.png>]
(486662 - 2)/4 = 121665
Das sind doch 'altbekannte' Zahlen!
Hier mal modulo 2^255-19:
| user15@o15:/tmp$ bc -q bc-eea
|
| ggT(4,57896044618658097711785492504343953926634992332820282019728792\
| 003956564819949)=1
| i=3
| b[0]=578960446186580977117854925043439539266349923328202820197287920\
| 03956564819949
| s[0]=-14474011154664524427946373126085988481658748083205070504932198\
| 000989141204987
| t[0]=1
also 1/4.
| user15@o15:/tmp$ bc -lq
| scale=0
| -14474011154664524427946373126085988481658748083205070504932198000989141204987+2^255-19
| 43422033463993573283839119378257965444976244249615211514796594002967\
| 423614962
| minv4=.
| minv4
| 43422033463993573283839119378257965444976244249615211514796594002967\
| 423614962
| (4866660 * minv4)%(2^255-19)
| 1216665
Da hatte ich mich vertippt. Das Ergebnis ist aber inter-
essant!
| (486660 * minv4)%(2^255-19)
| 121665
Paßt also. Auch ganz ohne "modulo":
| 121665*4
| 486660
Marcel
--
╭─╮ ╭────╮ ╭────╮ ╭──────────╮ ..51..╭────╮ ╭──╮
╭─╯ ╰─────╮ ..15..╰─╮ ╰──╯ ╰──╯ ╭───────╯ ╭────╯ ╰─╯ │
╯ ╭──────╯ ╭─╮ ╭───╯ ╭────────╯ ╭──╮ ╰───╮ ..61..│
╰─────────╯ ╰──╯ ╰──────────╯ ╰──────────╯ ..61..╰────╮
[<https://ybtra.de/div/2023h1/20230330c.png>]
>Nun haben wir die Konstanten aus dem Bild ...c.png bald
>alle durch. Es geht weiter (oder auch nicht ;-) mit der
>Quadratwurzel aus 486664 (mod 2^255-19 natürlich).
In RFC7748 fand ich noch:
>alle durch. Es geht weiter (oder auch nicht ;-) mit der
>Quadratwurzel aus 486664 (mod 2^255-19 natürlich).
(486662 - 2)/4 = 121665
Das sind doch 'altbekannte' Zahlen!
Hier mal modulo 2^255-19:
| user15@o15:/tmp$ bc -q bc-eea
|
| 003956564819949)=1
| i=3
| a[i]=1
| b[i]=0
|
| a[0]=4
| b[i]=0
|
| b[0]=578960446186580977117854925043439539266349923328202820197287920\
| 03956564819949
| s[0]=-14474011154664524427946373126085988481658748083205070504932198\
| 000989141204987
| t[0]=1
| a[0]*s[0]+b[0]*t[0]=1
s[0]+2^255-19 ist wieder das multiplikative Inverse von 4,
also 1/4.
| user15@o15:/tmp$ bc -lq
| scale=0
| 43422033463993573283839119378257965444976244249615211514796594002967\
| 423614962
| minv4=.
| minv4
| 43422033463993573283839119378257965444976244249615211514796594002967\
| 423614962
| (4866660 * minv4)%(2^255-19)
| 1216665
Da hatte ich mich vertippt. Das Ergebnis ist aber inter-
essant!
| (486660 * minv4)%(2^255-19)
| 121665
Paßt also. Auch ganz ohne "modulo":
| 121665*4
| 486660
Marcel
--
╭─╮ ╭────╮ ╭────╮ ╭──────────╮ ..51..╭────╮ ╭──╮
╭─╯ ╰─────╮ ..15..╰─╮ ╰──╯ ╰──╯ ╭───────╯ ╭────╯ ╰─╯ │
╯ ╭──────╯ ╭─╮ ╭───╯ ╭────────╯ ╭──╮ ╰───╮ ..61..│
╰─────────╯ ╰──╯ ╰──────────╯ ╰──────────╯ ..61..╰────╮
Marcel Logen
Apr 2, 2023, 7:25:29 AM4/2/23
to
Marcel Logen in de.test:
>In
><https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
>ist BTW die Rede von "sqrt(-486664)".
>
>Ich habe mit den Angaben aus Section 4.1 den Wurzel-Wert
>berechnen können, aber das kann es ja eigentlich nicht
>sein ...
Zunächst den Kehrwert von U(P)=9, also 1/U(P):
| user15@o15:/tmp$ bc -q bc-eea | tr '\012' '~' | sed -e 's/\\~//g' | tr '~' '\012'
|
| ggT(9,57896044618658097711785492504343953926634992332820282019728792003956564819949)=1
| i=5
| b[0]=57896044618658097711785492504343953926634992332820282019728792003956564819949
| s[0]=-25731575386070265649682441113041757300726663259031236453212796446202917697755
| t[0]=4
addieren:
| user15@o15:/tmp$ bc -lq
| scale=0
|
| -25731575386070265649682441113041757300726663259031236453212796446202917697755 + 2^255-19
| 32164469232587832062103051391302196625908329073789045566515995557753\
| 647122194
Dann gemäß RFC7748, 4.1.: sqrt(-486664) = X(P)*V(P)/U(P):
| ( 15112221349535400772501151409588531511454012693041857206046113283949847762202 * 43114425171068552920764898935933967039370386198203806730763910166200978582548 * 32164469232587832062103051391302196625908329073789045566515995557753647122194 ) % ( 2^255-19 )
| 68534752194975615815793572711976246424827900797856501970469582152896\
| 87604742
|
| wurzel = .
|
| ( wurzel^2 ) % ( 2^255-19 )
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564333285
|
| ( 2^255-19 - 57896044618658097711785492504343953926634992332820282019728792003956564333285) % ( 2^255-19)
| 486664
| user15@o15:/tmp$
Paßt also.
Es geht auch mit dem 'falschen' (unkorrigierten) V(P)
aus RFC7748:
| user15@o15:/tmp$ bc -lq
| scale=0
| ( 15112221349535400772501151409588531511454012693041857206046113283949847762202 * 14781619447589544791020593568409986887264606134616475288964881837755586237401 * 32164469232587832062103051391302196625908329073789045566515995557753647122194 ) % (2^255-19)
| 51042569399160536130206135233146329284152202253034631822681833788666\
| 877215207
| wurz=.
| wurz
| 51042569399160536130206135233146329284152202253034631822681833788666\
| 877215207
| (wurz^2)%(2^255-19)
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564333285
| 2^255-19 - .
| 486664
| user15@o15:/tmp$
"wurz" ist dann wohl - neben der obigen "wurzel" - die
zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
Aber wie man die beiden jetzt direkt ausrechnen kann ...?
(Ohne das Beispiel aus dem RFC zu bemühen.)
Grübel, grübel, grübel.
Wie gesagt: Mit dem Legendre-Symbol geht das wegen der
übergroßen Exponenten leider wohl nicht.
Marcel
--
╭───╮ ╭────╮ ╭────────────╮ ╭──────────────╮ ╭──╮ ..67..
╰─╮ ╰─╯ ╭─╯ ╰─────────╮ ╰────╮ ..38..╰───────╮ ╭───╯ │ ╰───────
───╯ ╭───╯ ╭─╮ ╭─╮ │ ╭────╯ ╭─╮ ╭───╮ ╭──╯ ╰──────╯ ..67..
╰──────╯ ╰───╯ ╰───╯ ╰───────╯ ╰─╯ ╰───╯ ..67..
>In
><https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
>ist BTW die Rede von "sqrt(-486664)".
>
>Ich habe mit den Angaben aus Section 4.1 den Wurzel-Wert
>berechnen können, aber das kann es ja eigentlich nicht
>sein ...
| user15@o15:/tmp$ bc -q bc-eea | tr '\012' '~' | sed -e 's/\\~//g' | tr '~' '\012'
|
| i=5
| a[i]=1
| b[i]=0
|
| a[0]=9
| b[i]=0
|
| b[0]=57896044618658097711785492504343953926634992332820282019728792003956564819949
| s[0]=-25731575386070265649682441113041757300726663259031236453212796446202917697755
| t[0]=4
| a[0]*s[0]+b[0]*t[0]=1
s[0] ist wieder der benötigte Wert. Noch 2^255-19 dazu
addieren:
| user15@o15:/tmp$ bc -lq
| scale=0
|
| 32164469232587832062103051391302196625908329073789045566515995557753\
| 647122194
Dann gemäß RFC7748, 4.1.: sqrt(-486664) = X(P)*V(P)/U(P):
| ( 15112221349535400772501151409588531511454012693041857206046113283949847762202 * 43114425171068552920764898935933967039370386198203806730763910166200978582548 * 32164469232587832062103051391302196625908329073789045566515995557753647122194 ) % ( 2^255-19 )
| 68534752194975615815793572711976246424827900797856501970469582152896\
| 87604742
|
| wurzel = .
|
| ( wurzel^2 ) % ( 2^255-19 )
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564333285
|
| ( 2^255-19 - 57896044618658097711785492504343953926634992332820282019728792003956564333285) % ( 2^255-19)
| 486664
| user15@o15:/tmp$
Paßt also.
Es geht auch mit dem 'falschen' (unkorrigierten) V(P)
aus RFC7748:
| user15@o15:/tmp$ bc -lq
| scale=0
| 51042569399160536130206135233146329284152202253034631822681833788666\
| 877215207
| wurz=.
| wurz
| 51042569399160536130206135233146329284152202253034631822681833788666\
| 877215207
| (wurz^2)%(2^255-19)
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564333285
| 2^255-19 - .
| 486664
| user15@o15:/tmp$
"wurz" ist dann wohl - neben der obigen "wurzel" - die
zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
Aber wie man die beiden jetzt direkt ausrechnen kann ...?
(Ohne das Beispiel aus dem RFC zu bemühen.)
Grübel, grübel, grübel.
Wie gesagt: Mit dem Legendre-Symbol geht das wegen der
übergroßen Exponenten leider wohl nicht.
Marcel
--
╭───╮ ╭────╮ ╭────────────╮ ╭──────────────╮ ╭──╮ ..67..
╰─╮ ╰─╯ ╭─╯ ╰─────────╮ ╰────╮ ..38..╰───────╮ ╭───╯ │ ╰───────
───╯ ╭───╯ ╭─╮ ╭─╮ │ ╭────╯ ╭─╮ ╭───╮ ╭──╯ ╰──────╯ ..67..
╰──────╯ ╰───╯ ╰───╯ ╰───────╯ ╰─╯ ╰───╯ ..67..
Marcel Logen
Apr 2, 2023, 7:44:49 AM4/2/23
to
Marcel Logen in de.test:
>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
>
>Aber wie man die beiden jetzt direkt ausrechnen kann ...?
>(Ohne das Beispiel aus dem RFC zu bemühen.)
>Grübel, grübel, grübel.
>
>Wie gesagt: Mit dem Legendre-Symbol geht das wegen der
>übergroßen Exponenten leider wohl nicht.
Wenn ich die Angaben aus
<https://de.wikipedia.org/wiki/Quadratwurzel#Quadratwurzeln_modulo_n>
richtig interpretiere, dann kann man wohl mit Probieren
zur Lösung kommen ...
Jedenfalls ist hier der Fall
p mod 4 = 1
gegeben:
| user15@o15:/tmp$ bc -lq
| scale=0
| (2^255-19)%4
| 1
| user15@o15:/tmp$
Ob das entsprechende Legendre-Symbol dann 1 ist, sei
mal dahingestellt. Ich kann es ja trotzdem mal probie-
ren.
Marcel
--
╭─╮ ╭─╮ ╭──────╮ ╭─╮ ╭─╮ ╭─╮ ..67..
│ │ ╭────╮ ╭─╯ ╰──╮ ╰───╮ ╰─╮ │ ╰───╯ │ ╭──╯ │ ..67..
─╯ ╰─╯ ╭─╯ │ │ ╭──╯ ╭─╯ ╭──╯ ..41..│ ╭─╯ ╭─╯ ╭─╮ ╭────╮
╰───╯ ╰───╯ ╰─────╯ ..41..╰─╯ ╰─────╯ ╰────╯ ╰
>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
>
>Aber wie man die beiden jetzt direkt ausrechnen kann ...?
>(Ohne das Beispiel aus dem RFC zu bemühen.)
>Grübel, grübel, grübel.
>
>Wie gesagt: Mit dem Legendre-Symbol geht das wegen der
>übergroßen Exponenten leider wohl nicht.
<https://de.wikipedia.org/wiki/Quadratwurzel#Quadratwurzeln_modulo_n>
richtig interpretiere, dann kann man wohl mit Probieren
zur Lösung kommen ...
Jedenfalls ist hier der Fall
p mod 4 = 1
gegeben:
| user15@o15:/tmp$ bc -lq
| scale=0
| 1
| user15@o15:/tmp$
Ob das entsprechende Legendre-Symbol dann 1 ist, sei
mal dahingestellt. Ich kann es ja trotzdem mal probie-
ren.
Marcel
--
╭─╮ ╭─╮ ╭──────╮ ╭─╮ ╭─╮ ╭─╮ ..67..
│ │ ╭────╮ ╭─╯ ╰──╮ ╰───╮ ╰─╮ │ ╰───╯ │ ╭──╯ │ ..67..
─╯ ╰─╯ ╭─╯ │ │ ╭──╯ ╭─╯ ╭──╯ ..41..│ ╭─╯ ╭─╯ ╭─╮ ╭────╮
╰───╯ ╰───╯ ╰─────╯ ..41..╰─╯ ╰─────╯ ╰────╯ ╰
Marcel Logen
Apr 3, 2023, 5:25:01 AM4/3/23
to
Marcel Logen in de.test:
>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
Jetzt mal das Produkt von "wurzel" und "wurz":
| user15@o15:/tmp$ bc -lq
| scale=0
| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
| 486664
| user15@o15:/tmp$
Also: +486664. Interessant.
>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
| user15@o15:/tmp$ bc -lq
| scale=0
| 486664
| user15@o15:/tmp$
Also: +486664. Interessant.
Marcel Logen
Apr 3, 2023, 5:41:51 AM4/3/23
to
Marcel Logen in de.test:
>>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
>
>Jetzt mal das Produkt von "wurzel" und "wurz":
>
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 486664
>| user15@o15:/tmp$
>
>Also: +486664. Interessant.
Ich lese gerade in der englischen Wikipedia
>>"wurz" ist dann wohl - neben der obigen "wurzel" - die
>>zweite Quadratwurzel aus -486664 (mod 2^255 - 19).
>
>Jetzt mal das Produkt von "wurzel" und "wurz":
>
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 486664
>| user15@o15:/tmp$
>
>Also: +486664. Interessant.
<https://en.wikipedia.org/wiki/Square_root#In_integral_domains,_including_fields>,
daß
wurz = -wurzel
sein muß.
| user15@o15:/tmp$ bc -lq
| scale=0
| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
| 486664
| 0
| user15@o15:/tmp$
Bleibt noch die Frage: Was ist sqrt(+486664)?
<https://ybtra.de/div/2023h1/20230330c.png>
Marcel
--
╭──╮ ╭─────────────╮ ..56..╭──────────
╭───╯ ╰─────╯ ╭───────╯ ╭──╮ ..51..╭─╮ ╰─────╮
╯ ╭─────╯ ╭─╮ ╭─╮ ..35..╭─╯ │ ╭─╮ ╭─╮ │ ╰────────╯
╰─────────╯ ╰───╯ ╰────────╯ ╰─╯ ╰─╯ ╰──╯ ..67..
Marcel Logen
Apr 4, 2023, 9:27:51 AM4/4/23
to
Marcel Logen in de.test:
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 486664
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 + 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 0
>| user15@o15:/tmp$
>
>Bleibt noch die Frage: Was ist sqrt(+486664)?
>
><https://ybtra.de/div/2023h1/20230330c.png>
Und: Was ist sqrt(-1) mod (2^255-19)?
Siehe Bild: "[...] since -1 is a square in Fq".
q = 2^255 - 19
Fq = der endliche Körper der Restklassen modulo q
<https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
Probieren hilft bei diesen großen Zahlen wohl nicht,
denke ich.
Marcel
--
╭─────╮ ╭─╮ ╭───╮ ╭──╮ ╭───╮ ..61..╭────╮
...2..╭─╮ ╰───╮ ╰─╮ ╭──╯ ╰─╯ ╰─╯ ╰────╯ ╰────╮ ╭──────────╯ │
╭─╯ ╰───╮ ╰─╮ │ ╰───────╮ ..48..╰─╯ ╭────────────╯
╭────╯ ╰────╯ ╰──────────╯ ..53..╰─────────────
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 * 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 486664
>| ( 6853475219497561581579357271197624642482790079785650197046958215289687604742 + 51042569399160536130206135233146329284152202253034631822681833788666877215207 ) % (2^255-19)
>| 0
>| user15@o15:/tmp$
>
>Bleibt noch die Frage: Was ist sqrt(+486664)?
>
><https://ybtra.de/div/2023h1/20230330c.png>
Siehe Bild: "[...] since -1 is a square in Fq".
q = 2^255 - 19
Fq = der endliche Körper der Restklassen modulo q
<https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
Probieren hilft bei diesen großen Zahlen wohl nicht,
denke ich.
Marcel
--
╭─────╮ ╭─╮ ╭───╮ ╭──╮ ╭───╮ ..61..╭────╮
...2..╭─╮ ╰───╮ ╰─╮ ╭──╯ ╰─╯ ╰─╯ ╰────╯ ╰────╮ ╭──────────╯ │
╭─╯ ╰───╮ ╰─╮ │ ╰───────╮ ..48..╰─╯ ╭────────────╯
╭────╯ ╰────╯ ╰──────────╯ ..53..╰─────────────
Marcel Logen
Apr 4, 2023, 12:20:15 PM4/4/23
to
Marcel Logen in de.test:
>>Bleibt noch die Frage: Was ist sqrt(+486664)?
>>
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>Und: Was ist sqrt(-1) mod (2^255-19)?
>Siehe Bild: "[...] since -1 is a square in Fq".
>
>q = 2^255 - 19
>Fq = der endliche Körper der Restklassen modulo q
><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>
>Probieren hilft bei diesen großen Zahlen wohl nicht,
>denke ich.
Bei einer Suche bin ich auf ein Vorlesungsskript ge-
stoßen, in dem die Rede vom "Tonelli-Shanks-Algorith-
mus" ist:
<https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
Vielleicht kann man ja damit etwas erreichen ...
Marcel
--
╭─╮ ╭─╮ ╭────╮ ╭───╮ ╭──╮ ..67..
...1..╭─╮ │ ╰──────╯ ╰─╮ ╭──╯ ╭─╯ ╭─╮ ╭───╯ ╰─╮ ╭──╯ ╰─╮ ╭─╮
╭─╮ ╭─╯ │ ╭─╯ ..20..╰──╯ ╰───╯ ╰─╯ ╭───╯ ╰───╮ ╰─╮ │ ╰──
╯ ╰─╯ ╰─╯ ..43..╰──────────╯ ╰─╯
>>Bleibt noch die Frage: Was ist sqrt(+486664)?
>>
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>Und: Was ist sqrt(-1) mod (2^255-19)?
>Siehe Bild: "[...] since -1 is a square in Fq".
>
>q = 2^255 - 19
>Fq = der endliche Körper der Restklassen modulo q
><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>
>Probieren hilft bei diesen großen Zahlen wohl nicht,
>denke ich.
stoßen, in dem die Rede vom "Tonelli-Shanks-Algorith-
mus" ist:
<https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
Vielleicht kann man ja damit etwas erreichen ...
Marcel
--
╭─╮ ╭─╮ ╭────╮ ╭───╮ ╭──╮ ..67..
...1..╭─╮ │ ╰──────╯ ╰─╮ ╭──╯ ╭─╯ ╭─╮ ╭───╯ ╰─╮ ╭──╯ ╰─╮ ╭─╮
╭─╮ ╭─╯ │ ╭─╯ ..20..╰──╯ ╰───╯ ╰─╯ ╭───╯ ╰───╮ ╰─╮ │ ╰──
╯ ╰─╯ ╰─╯ ..43..╰──────────╯ ╰─╯
Marcel Logen
Apr 4, 2023, 12:22:09 PM4/4/23
to
Marcel Logen in de.test:
>>Bleibt noch die Frage: Was ist sqrt(+486664)?
>>
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>Und: Was ist sqrt(-1) mod (2^255-19)?
>Siehe Bild: "[...] since -1 is a square in Fq".
>
>q = 2^255 - 19
>Fq = der endliche Körper der Restklassen modulo q
><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>
>Probieren hilft bei diesen großen Zahlen wohl nicht,
>denke ich.
Bei einer Suche bin ich auf ein Vorlesungsskript [1] ge-
stoßen, in dem die Rede vom "Tonelli-Shanks-Algorithmus"
[supersedes]
--
│ ╭─────╮ ╭──╮ ╭────╮ ╭──╮ ╭─────╮..60..╭──╮ ╭─
│ ╰───╮ ╰──╯ │ ╰─╮ ╰────╮ ╭──╮..37..╭─╮ │ ╰──╯ ╰────╮ │ ╰─╯
│ ╭──╯ │ ╭─╯ ╭─╯ ╭─╯ │ ╭────╯ │ │ ╰─╯..67..
╰───╯ ╰──╯ ╰───╯ ╰─╯ ╰─╯ ..67..
>>Bleibt noch die Frage: Was ist sqrt(+486664)?
>>
>><https://ybtra.de/div/2023h1/20230330c.png>
>
>Und: Was ist sqrt(-1) mod (2^255-19)?
>Siehe Bild: "[...] since -1 is a square in Fq".
>
>q = 2^255 - 19
>Fq = der endliche Körper der Restklassen modulo q
><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>
>Probieren hilft bei diesen großen Zahlen wohl nicht,
>denke ich.
stoßen, in dem die Rede vom "Tonelli-Shanks-Algorithmus"
ist:
<https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
Vielleicht kann man ja damit etwas erreichen ...
Marcel
[1] <https://www.math.uni-bielefeld.de/~frettloe/teach/krypto/krypto2019.pdf>
<https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
Vielleicht kann man ja damit etwas erreichen ...
Marcel
[supersedes]
--
│ ╭─────╮ ╭──╮ ╭────╮ ╭──╮ ╭─────╮..60..╭──╮ ╭─
│ ╰───╮ ╰──╯ │ ╰─╮ ╰────╮ ╭──╮..37..╭─╮ │ ╰──╯ ╰────╮ │ ╰─╯
│ ╭──╯ │ ╭─╯ ╭─╯ ╭─╯ │ ╭────╯ │ │ ╰─╯..67..
╰───╯ ╰──╯ ╰───╯ ╰─╯ ╰─╯ ..67..
Marcel Logen
Apr 4, 2023, 3:26:10 PM4/4/23
to
Marcel Logen in de.test:
>>q = 2^255 - 19
>>Fq = der endliche Körper der Restklassen modulo q
>><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>>
>>Probieren hilft bei diesen großen Zahlen wohl nicht,
>>denke ich.
>
>Bei einer Suche bin ich auf ein Vorlesungsskript [1] ge-
>stoßen, in dem die Rede vom "Tonelli-Shanks-Algorithmus"
>ist:
>
><https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
>
>Vielleicht kann man ja damit etwas erreichen ...
Da gibt es aber auch sehr große Exponenten.
Inzwischen habe ich
<https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
gefunden.
Da müßte ich dann wohl mal etwas Passendes programmieren.
Marcel
--
╰─╮ ╭──────────────╮ ╭───╮ ╭─╮ ..55..╭──────╮
│ ╭──╮ ╰────────╮ ╰──╯ ╰──╯ ╰─╮ ..55..╰──╮ │
╰─╯ │ ╭─╯ ..32..╭─╯ ╭──╮ ╭─╮ ╭─╮ ╭───╯ ╰─╮
╰─────────╯ ╰───╯ ╰─────╯ ╰─╯ ╰──╯ ..64..╰─╮
>>q = 2^255 - 19
>>Fq = der endliche Körper der Restklassen modulo q
>><https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper>
>>
>>Probieren hilft bei diesen großen Zahlen wohl nicht,
>>denke ich.
>
>Bei einer Suche bin ich auf ein Vorlesungsskript [1] ge-
>stoßen, in dem die Rede vom "Tonelli-Shanks-Algorithmus"
>ist:
>
><https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
>
>Vielleicht kann man ja damit etwas erreichen ...
Inzwischen habe ich
<https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
gefunden.
Da müßte ich dann wohl mal etwas Passendes programmieren.
Marcel
--
╰─╮ ╭──────────────╮ ╭───╮ ╭─╮ ..55..╭──────╮
│ ╭──╮ ╰────────╮ ╰──╯ ╰──╯ ╰─╮ ..55..╰──╮ │
╰─╯ │ ╭─╯ ..32..╭─╯ ╭──╮ ╭─╮ ╭─╮ ╭───╯ ╰─╮
╰─────────╯ ╰───╯ ╰─────╯ ╰─╯ ╰──╯ ..64..╰─╮
Marcel Logen
Apr 4, 2023, 7:11:44 PM4/4/23
to
Marcel Logen in de.test:
>><https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
>>
>>Vielleicht kann man ja damit etwas erreichen ...
>
>Da gibt es aber auch sehr große Exponenten.
Diesen Algorithmus brauche ich wahrscheinlich gar nicht,
denn:
>Inzwischen habe ich
><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>gefunden.
>
>Da müßte ich dann wohl mal etwas Passendes programmieren.
Habe schon mal angefangen. Ich kann jetzt Legendresymbole
recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
ja die Exponenten sehr groß sind!).
<https://de.wikipedia.org/wiki/Quadratwurzel#Berechnung_f%C3%BCr_den_Fall_p_mod_4_=_1>
| user15@o15:/tmp$ bc -lq
| scale=0
| (2^255-19)%4
| 1
Es fehlen mir jetzt für die Quadratwurzel-Berechnung noch
die Hilfswerte W_n. Das Problem sollte sich aber lösen las-
sen.
Morgen dann vielleicht. :-)
Marcel
--
│ ╭─╮ ..28..╭───╮ ╭──╮ ╭─╮ ╭────╮ ╭───╮ ╭───╮
│ │ ╰─╮ ..28..╰─╮ ╰─╯ │ │ ╰─╯ │ ╰─╮ │ │ ╰───╮
│ ╭─╯ │ ╭─╮ ╭───╮ ╭──────╯ ╰─╯..46..╭─╯ ╭─╯ │ ╰────╮ ╰
╰─────╯ ╰───╯ ╰──╯ ╰──╯ ..46..╰────╯ ╰───────╯
>><https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm#The_algorithm>
>>
>>Vielleicht kann man ja damit etwas erreichen ...
>
>Da gibt es aber auch sehr große Exponenten.
denn:
>Inzwischen habe ich
><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>gefunden.
>
>Da müßte ich dann wohl mal etwas Passendes programmieren.
recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
ja die Exponenten sehr groß sind!).
<https://de.wikipedia.org/wiki/Quadratwurzel#Berechnung_f%C3%BCr_den_Fall_p_mod_4_=_1>
| user15@o15:/tmp$ bc -lq
| scale=0
| 1
Es fehlen mir jetzt für die Quadratwurzel-Berechnung noch
die Hilfswerte W_n. Das Problem sollte sich aber lösen las-
sen.
Morgen dann vielleicht. :-)
Marcel
--
│ ╭─╮ ..28..╭───╮ ╭──╮ ╭─╮ ╭────╮ ╭───╮ ╭───╮
│ │ ╰─╮ ..28..╰─╮ ╰─╯ │ │ ╰─╯ │ ╰─╮ │ │ ╰───╮
│ ╭─╯ │ ╭─╮ ╭───╮ ╭──────╯ ╰─╯..46..╭─╯ ╭─╯ │ ╰────╮ ╰
╰─────╯ ╰───╯ ╰──╯ ╰──╯ ..46..╰────╯ ╰───────╯
Marcel Logen
Apr 5, 2023, 9:03:33 AM4/5/23
to
Marcel Logen in de.test:
[...]
[...]
>>Inzwischen habe ich
>><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>>gefunden.
>>
>>Da müßte ich dann wohl mal etwas Passendes programmieren.
>
>Habe schon mal angefangen. Ich kann jetzt Legendresymbole
>recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
>ja die Exponenten sehr groß sind!).
Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>>gefunden.
>>
>>Da müßte ich dann wohl mal etwas Passendes programmieren.
>
>Habe schon mal angefangen. Ich kann jetzt Legendresymbole
>recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
>ja die Exponenten sehr groß sind!).
auf der Kommandozeile übergeben kann, jedenfalls nicht
*vor* Ausführung des Scripts. Ich muß die Werte also in
das Script schreiben, was IMHO sehr umständlich ist.
Hier mal zwei Beispiele für Legendre-Symbole:
1.
| user15@o15:~/ybtra-o15$ cat bc-legendre05
| # <https://de.wikipedia.org/wiki/Legendre-Symbol>
| # <https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
|
| scale=0
| basis0=486664
| primz=2^255-19
|
| define ls(x,p) {
| lesy=1
| exponent=(p-1)/2
| basis=x
| while ( exponent ) {
| if ( (exponent % 2) == 1 ) lesy = ( lesy * basis ) % p
| exponent /= 2
| basis = ( basis ^ 2 ) % p
| }
| return lesy
| }
|
| legendresy=ls(basis0,primz)
| if(legendresy==primz-1)legendresy-=primz
| legendresy
|
| quit
|
| user15@o15:~/ybtra-o15$ bc -lq bc-legendre05
| 1
| user15@o15:~/ybtra-o15$
2.
| user15@o15:~/ybtra-o15$ head bc-legendre05
| # <https://de.wikipedia.org/wiki/Legendre-Symbol>
| # <https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
|
| scale=0
| basis0=2^2-4*486664
| primz=2^255-19
|
| define ls(x,p) {
| lesy=1
| exponent=(p-1)/2
| user15@o15:~/ybtra-o15$ bc -lq bc-legendre05
| -1
| user15@o15:~/ybtra-o15$
><https://de.wikipedia.org/wiki/Quadratwurzel#Berechnung_f%C3%BCr_den_Fall_p_mod_4_=_1>
>
>| user15@o15:/tmp$ bc -lq
>| scale=0
>| (2^255-19)%4
>| 1
>
>Es fehlen mir jetzt für die Quadratwurzel-Berechnung noch
>die Hilfswerte W_n. Das Problem sollte sich aber lösen las-
>sen.
>
>Morgen dann vielleicht. :-)
Ich mache immer alles morgen."
Marcel
--
╭──╮ ╭─────╮ ╭─────────╮ ╭────────╮ ..50..╭──────────╮ │
───╯ │ ╭───╮ │ ╭─╯ ╰─╮ ╭────╯ ╰────╮ │ ..50..╰───╮ ╭───╯ ╭──╯
...1..╰─╯ ╰──╯ ╰──╮ ╭──╯ ╰───────╮ │ ╰───╮ ╭─╮ ╭─╯ ╰─────╯
╰─╯ ╰────╯ ╰─╯ ╰─╯ ..67..
Marcel Logen
Apr 5, 2023, 9:17:05 AM4/5/23
to
Marcel Logen in de.test:
>>>Inzwischen habe ich
>>><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>>>gefunden.
>>>
>>>Da müßte ich dann wohl mal etwas Passendes programmieren.
>>
>>Habe schon mal angefangen. Ich kann jetzt Legendresymbole
>>recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
>>ja die Exponenten sehr groß sind!).
>
>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>auf der Kommandozeile übergeben kann, jedenfalls nicht
>*vor* Ausführung des Scripts. Ich muß die Werte also in
>das Script schreiben, was IMHO sehr umständlich ist.
Ich sehe gerade eben in der man page von GNU-bc, daß es
als extension die Funktion "read( )" gibt. Vermutlich kann
ich damit das Gewünschte erreichen.
Marcel
--
╭─╮ ╭─╮ ╭────╮ ╭─╮ ..29..╭─╮ ╭─────╮ ╭───╮ ╭───╮ ╭──╮
─╮ │ ╰──╯ ╰─╯ ╭─╯ │ │ ╭─╮ ╭───╯ │ ╰──╮ ╰──╯ ╰─╮ ╰─╮ │ │ ╰──╮
╰─╯ ...8..╭─╯ │ │ │ ╰──╯ ╰──╮ ╰───╮ ╭────╯ ╭─╯ ╰─╯ ╭──╯
╰─────╯ ╰───╯ ╰──────╯ ╰───────╯ ..61..╰────╮
>>>Inzwischen habe ich
>>><https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin%C3%A4re_Modulo-Exponentiation>
>>>gefunden.
>>>
>>>Da müßte ich dann wohl mal etwas Passendes programmieren.
>>
>>Habe schon mal angefangen. Ich kann jetzt Legendresymbole
>>recht flott mit Hilfe eines bc-Scripts berechnen (obwohl
>>ja die Exponenten sehr groß sind!).
>
>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>auf der Kommandozeile übergeben kann, jedenfalls nicht
>*vor* Ausführung des Scripts. Ich muß die Werte also in
>das Script schreiben, was IMHO sehr umständlich ist.
als extension die Funktion "read( )" gibt. Vermutlich kann
ich damit das Gewünschte erreichen.
Marcel
--
╭─╮ ╭─╮ ╭────╮ ╭─╮ ..29..╭─╮ ╭─────╮ ╭───╮ ╭───╮ ╭──╮
─╮ │ ╰──╯ ╰─╯ ╭─╯ │ │ ╭─╮ ╭───╯ │ ╰──╮ ╰──╯ ╰─╮ ╰─╮ │ │ ╰──╮
╰─╯ ...8..╭─╯ │ │ │ ╰──╯ ╰──╮ ╰───╮ ╭────╯ ╭─╯ ╰─╯ ╭──╯
╰─────╯ ╰───╯ ╰──────╯ ╰───────╯ ..61..╰────╮
Marcel Logen
Apr 5, 2023, 9:39:48 AM4/5/23
to
Marcel Logen in de.test:
>>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>>auf der Kommandozeile übergeben kann, jedenfalls nicht
>>*vor* Ausführung des Scripts. Ich muß die Werte also in
>>das Script schreiben, was IMHO sehr umständlich ist.
>
>Ich sehe gerade eben in der man page von GNU-bc, daß es
>als extension die Funktion "read( )" gibt. Vermutlich kann
>ich damit das Gewünschte erreichen.
Noch nicht ganz! Man kann da wohl nur reine Zahlen ein-
lesen, keinen 'Programmcode' wie mit -e beim BSD-bc, also
leider nicht "a[0]=5^13;b[0]=2^255-19".
Hm. Immer noch doof.
Marcel
--
╭──╮ ╭────╮ ..53..╭───╮ ╭───╮
╮ ╭───╮ ╭──╯ ╰───╮ ╭───╮ ╰─╮ │ ╭─╮ ..53..│ │ ╰─╮ ╰──
│ ╭─╯ ╰─╯ ..15..│ │ ╰─╮ │ ╰─╮ │ ╰─╮ ╭────╮ ╭─╯ │ ╭─╯
╰─╯ ╰───╯ ╰──╯ ╰──╯ ╰──╯ ╰──╯ ╰──╯..67..
>>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>>auf der Kommandozeile übergeben kann, jedenfalls nicht
>>*vor* Ausführung des Scripts. Ich muß die Werte also in
>>das Script schreiben, was IMHO sehr umständlich ist.
>
>Ich sehe gerade eben in der man page von GNU-bc, daß es
>als extension die Funktion "read( )" gibt. Vermutlich kann
>ich damit das Gewünschte erreichen.
lesen, keinen 'Programmcode' wie mit -e beim BSD-bc, also
leider nicht "a[0]=5^13;b[0]=2^255-19".
Hm. Immer noch doof.
Marcel
--
╭──╮ ╭────╮ ..53..╭───╮ ╭───╮
╮ ╭───╮ ╭──╯ ╰───╮ ╭───╮ ╰─╮ │ ╭─╮ ..53..│ │ ╰─╮ ╰──
│ ╭─╯ ╰─╯ ..15..│ │ ╰─╮ │ ╰─╮ │ ╰─╮ ╭────╮ ╭─╯ │ ╭─╯
╰─╯ ╰───╯ ╰──╯ ╰──╯ ╰──╯ ╰──╯ ╰──╯..67..
Marcel Logen
Apr 5, 2023, 9:45:55 AM4/5/23
to
Marcel Logen in de.test:
>>>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>>>auf der Kommandozeile übergeben kann, jedenfalls nicht
>>>*vor* Ausführung des Scripts. Ich muß die Werte also in
>>>das Script schreiben, was IMHO sehr umständlich ist.
>>
>>Ich sehe gerade eben in der man page von GNU-bc, daß es
>>als extension die Funktion "read( )" gibt. Vermutlich kann
>>ich damit das Gewünschte erreichen.
>
>Noch nicht ganz! Man kann da wohl nur reine Zahlen ein-
>lesen, keinen 'Programmcode' wie mit -e beim BSD-bc, also
>leider nicht "a[0]=5^13;b[0]=2^255-19".
Hier mal die man page vom OpenBSD-bc:
>>>Blöd ist beim GNU-bc aber, daß ich keine Variablenwerte
>>>auf der Kommandozeile übergeben kann, jedenfalls nicht
>>>*vor* Ausführung des Scripts. Ich muß die Werte also in
>>>das Script schreiben, was IMHO sehr umständlich ist.
>>
>>Ich sehe gerade eben in der man page von GNU-bc, daß es
>>als extension die Funktion "read( )" gibt. Vermutlich kann
>>ich damit das Gewünschte erreichen.
>
>Noch nicht ganz! Man kann da wohl nur reine Zahlen ein-
>lesen, keinen 'Programmcode' wie mit -e beim BSD-bc, also
>leider nicht "a[0]=5^13;b[0]=2^255-19".
<https://man.openbsd.org/bc>
Marcel
--
╭────────╮ ╭────────╮ ╭──╮ ╭───╮ ..67..
╭───╮ ╰───╮ ╭─╯ ╰────╮ ╰────╮ ╭──╯ ╰─╯ ╰─────╮ ╭────╮ ..67..
│ ╰───╮ │ ╰───────╮ │ ╰──╯ ..52..╰─╯ │ ╭────
──╯ ╰───╯ ╰─╯ ..59..╰──╯
Marcel Logen
Apr 5, 2023, 1:58:06 PM4/5/23
to
Marcel Logen in de.test:
><https://de.wikipedia.org/wiki/Quadratwurzel#Berechnung_f%C3%BCr_den_Fall_p_mod_4_=_1>
[...]
>Es fehlen mir jetzt für die Quadratwurzel-Berechnung noch
>die Hilfswerte W_n. Das Problem sollte sich aber lösen las-
>sen.
Inzwischen habe ich gemerkt, daß die Indizes der W_n sehr
groß werden! Z. B. (p+3)/4 mit p = 2^255-19. Da kommt dann
wohl kein Script/Programm mehr mit. Grmpf.
| user15@o15:/tmp$ echo 'scale=0; p=2^255-19; p; (p+3)/4' | bc | tr '\012' '~' | sed -e 's/\\~//g' | tr '~' '\012'
| 57896044618658097711785492504343953926634992332820282019728792003956564819949
| 14474011154664524427946373126085988481658748083205070504932198000989141204988
| user15@o15:/tmp$
>Morgen dann vielleicht. :-)
Wahrscheinlich doch nicht.
Offen sind immer noch diese Berechnungen:
sqrt(486664) mod (2^255 - 19)
sqrt(-1) mod (2^255 -19)
Tja.
Wieder zurück zu "Tonelli-Shanks"?
Marcel
--
╭─╮ ╭─────╮ ╭──╮ ╭─────╮ ╭─╮ ╭─╮ ..67..
──╯ ╰─╮ ╰───╮ │ ╭───╮ ╭─╮ │ ╰─╮ ╭─╯ ╭─╮ ╰─╯ │ ╭─╯ │ ╭──╮
╭────╯ ╭────╯ ╰────╯ ╰──╯ ╰─╯ ╭─╯ ╰───╯ ╰─╮ ╰───╯ ╰───╯ ╰─╮ ╭
╰──────╯ ╰────────────╯ ..63..╰──╯
><https://de.wikipedia.org/wiki/Quadratwurzel#Berechnung_f%C3%BCr_den_Fall_p_mod_4_=_1>
[...]
>Es fehlen mir jetzt für die Quadratwurzel-Berechnung noch
>die Hilfswerte W_n. Das Problem sollte sich aber lösen las-
>sen.
groß werden! Z. B. (p+3)/4 mit p = 2^255-19. Da kommt dann
wohl kein Script/Programm mehr mit. Grmpf.
| user15@o15:/tmp$ echo 'scale=0; p=2^255-19; p; (p+3)/4' | bc | tr '\012' '~' | sed -e 's/\\~//g' | tr '~' '\012'
| 57896044618658097711785492504343953926634992332820282019728792003956564819949
| 14474011154664524427946373126085988481658748083205070504932198000989141204988
| user15@o15:/tmp$
>Morgen dann vielleicht. :-)
Wahrscheinlich doch nicht.
Offen sind immer noch diese Berechnungen:
sqrt(486664) mod (2^255 - 19)
sqrt(-1) mod (2^255 -19)
Tja.
Wieder zurück zu "Tonelli-Shanks"?
Marcel
--
╭─╮ ╭─────╮ ╭──╮ ╭─────╮ ╭─╮ ╭─╮ ..67..
──╯ ╰─╮ ╰───╮ │ ╭───╮ ╭─╮ │ ╰─╮ ╭─╯ ╭─╮ ╰─╯ │ ╭─╯ │ ╭──╮
╭────╯ ╭────╯ ╰────╯ ╰──╯ ╰─╯ ╭─╯ ╰───╯ ╰─╮ ╰───╯ ╰───╯ ╰─╮ ╭
╰──────╯ ╰────────────╯ ..63..╰──╯
Marcel Logen
Apr 5, 2023, 2:59:30 PM4/5/23
to
Marcel Logen in de.test:
>Offen sind immer noch diese Berechnungen:
>
> sqrt(486664) mod (2^255 - 19)
> sqrt(-1) mod (2^255 -19)
>
>Tja.
>
>Wieder zurück zu "Tonelli-Shanks"?
Damit erhalte ich mit etwas Mühe:
sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
Probe:
| user15@o15:~/ybtra-o15$ bc -lq
| scale=0
| ( 48802004052532134862652268456126542835229456083994414501085850622543968879637^2)%(2^255-19)
| 486664
| -48802004052532134862652268456126542835229456083994414501085850622543968879637+2^255-19
| 90940405661259628491332240482174110914055362488258675186429413814125\
| 95940312
| (last^2)%(2^255-19)
| 486664
| user15@o15:~/ybtra-o15$
Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
in Zusammenhang standen.
sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
Marcel
--
╭───╮ ╭─╮ ╭──╮ ╭───────────╮ ..66..│
╮ ╭──────────╯ ╰──╯ ╰─╯ ╰─╮ ..41..╰────────╮ ╰──╮ ╭─────╯
│ ╰──╮ │ ╭──╮ ╭──╮ ╭─╮ │ ╭──╯ │..67..
╰─────╯ ╰────────╯ ╰─╯ ╰──╯ ╰──╯ ╰──────╯..67..
>Offen sind immer noch diese Berechnungen:
>
> sqrt(486664) mod (2^255 - 19)
> sqrt(-1) mod (2^255 -19)
>
>Tja.
>
>Wieder zurück zu "Tonelli-Shanks"?
sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
Probe:
| user15@o15:~/ybtra-o15$ bc -lq
| scale=0
| ( 48802004052532134862652268456126542835229456083994414501085850622543968879637^2)%(2^255-19)
| 486664
| -48802004052532134862652268456126542835229456083994414501085850622543968879637+2^255-19
| 90940405661259628491332240482174110914055362488258675186429413814125\
| 95940312
| (last^2)%(2^255-19)
| 486664
| user15@o15:~/ybtra-o15$
Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
in Zusammenhang standen.
sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
Marcel
--
╭───╮ ╭─╮ ╭──╮ ╭───────────╮ ..66..│
╮ ╭──────────╯ ╰──╯ ╰─╯ ╰─╮ ..41..╰────────╮ ╰──╮ ╭─────╯
│ ╰──╮ │ ╭──╮ ╭──╮ ╭─╮ │ ╭──╯ │..67..
╰─────╯ ╰────────╯ ╰─╯ ╰──╯ ╰──╯ ╰──────╯..67..
Marcel Logen
Apr 6, 2023, 6:58:39 AM4/6/23
to
Marcel Logen in de.test:
> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>
>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
[...]
>Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
>in Zusammenhang standen.
Sieht nicht so aus: <news:20230402...@o15.ybtra.de>.
>sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
Das entsprechende Legendre-Symbol hat den Wert 1; das sollte
dann wohl eigentlich heißen, daß es Quadratwurzeln von -1 gibt.
<https://de.wikipedia.org/wiki/Legendre-Symbol>
<https://de.wikipedia.org/wiki/Quadratischer_Rest#Der_Fall_von_Primzahlen_und_das_Legendre-Symbol>
Hm. Darüber muß ich noch mal verschärft nachdenken.
| user15@o15:~/ybtra-o15$ echo '-1 + 2^255-19' | bc -lq
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819948
| user15@o15:~/ybtra-o15$ echo '57896044618658097711785492504343953926634992332820282019728792003956564819948' | bc -lq bc-legendre06
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819948
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819949
| 1
^ Legendre-Symbol für -1 (mit p = 2^255 -19)
In einer ruhigen Stunde werde ich mal den Tonelli-Shanks-
Algorithmus auf -1 anwenden und hoffe, daß dann ein Wert
für die Wurzel(n) herauskommt.
> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>
>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
>Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
>in Zusammenhang standen.
>sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
dann wohl eigentlich heißen, daß es Quadratwurzeln von -1 gibt.
<https://de.wikipedia.org/wiki/Legendre-Symbol>
<https://de.wikipedia.org/wiki/Quadratischer_Rest#Der_Fall_von_Primzahlen_und_das_Legendre-Symbol>
Hm. Darüber muß ich noch mal verschärft nachdenken.
| user15@o15:~/ybtra-o15$ echo '-1 + 2^255-19' | bc -lq
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819948
| user15@o15:~/ybtra-o15$ echo '57896044618658097711785492504343953926634992332820282019728792003956564819948' | bc -lq bc-legendre06
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819948
| 57896044618658097711785492504343953926634992332820282019728792003956\
| 564819949
| 1
^ Legendre-Symbol für -1 (mit p = 2^255 -19)
In einer ruhigen Stunde werde ich mal den Tonelli-Shanks-
Algorithmus auf -1 anwenden und hoffe, daß dann ein Wert
für die Wurzel(n) herauskommt.
Marcel Logen
Apr 6, 2023, 6:51:21 PM4/6/23
to
Marcel Logen in de.test:
>> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>
>>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
>
>[...]
>
>>Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
>>in Zusammenhang standen.
>
>Sieht nicht so aus: <news:20230402...@o15.ybtra.de>.
Es fehlt noch die Berechnung von sqrt(-486664) mit Tonelli-
>> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>
>>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
>
>[...]
>
>>Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
>>in Zusammenhang standen.
>
>Sieht nicht so aus: <news:20230402...@o15.ybtra.de>.
Shanks. Anschließend die Werte vergleichen.
>>sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
>
>Das entsprechende Legendre-Symbol hat den Wert 1; das sollte
>dann wohl eigentlich heißen, daß es Quadratwurzeln von -1 gibt.
>
><https://de.wikipedia.org/wiki/Legendre-Symbol>
><https://de.wikipedia.org/wiki/Quadratischer_Rest#Der_Fall_von_Primzahlen_und_das_Legendre-Symbol>
>
>Hm. Darüber muß ich noch mal verschärft nachdenken.
<https://de.wikipedia.org/wiki/Quadratisches_Reziprozit%C3%A4tsgesetz>
>| user15@o15:~/ybtra-o15$ echo '-1 + 2^255-19' | bc -lq
>| 57896044618658097711785492504343953926634992332820282019728792003956\
>| 564819948
>
>| user15@o15:~/ybtra-o15$ echo '57896044618658097711785492504343953926634992332820282019728792003956564819948' | bc -lq bc-legendre06
>| 57896044618658097711785492504343953926634992332820282019728792003956\
>| 564819948
>| 57896044618658097711785492504343953926634992332820282019728792003956\
>| 564819949
>| 1
> ^ Legendre-Symbol für -1 (mit p = 2^255 -19)
>
>In einer ruhigen Stunde werde ich mal den Tonelli-Shanks-
>Algorithmus auf -1 anwenden und hoffe, daß dann ein Wert
>für die Wurzel(n) herauskommt.
Marcel
--
╮ ..30..╭───╮ ╭─────────────╮ ╭────╮
╰─╮ ╰─╮ ╰─╯ ..50..╰─╮ │ ╭─╯
╰─╮ ╭─╮ ╭───────╮ ╭───────╮ ╭──╯ ..46..╭─────╯ ╭─╯ ╰───╮
╰──╯ ╰───╯ ╰─╯ ╰──╯ ╰───────╯ ..63..╰──╮
Marcel Logen
Apr 8, 2023, 1:16:04 PM4/8/23
to
Marcel Logen in de.test:
>>> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>>
>>>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
>>> sqrt(486664) mod (2^255-19) = +/- 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>>
>>>Also 48802004052532134862652268456126542835229456083994414501085850622543968879637
>>>und 9094040566125962849133224048217411091405536248825867518642941381412595940312.
>>>Ich muß mal schauen, ob diese Zahlen nicht schon mit -486664
>>>in Zusammenhang standen.
>>
>>Sieht nicht so aus: <news:20230402...@o15.ybtra.de>.
>
>Es fehlt noch die Berechnung von sqrt(-486664) mit Tonelli-
>Shanks. Anschließend die Werte vergleichen.
Ich komme mit Tonelli-Shanks auf die Wurzeln
>>>in Zusammenhang standen.
>>
>>Sieht nicht so aus: <news:20230402...@o15.ybtra.de>.
>
>Es fehlt noch die Berechnung von sqrt(-486664) mit Tonelli-
>Shanks. Anschließend die Werte vergleichen.
6853475219497561581579357271197624642482790079785650197046958215289687604742
und
51042569399160536130206135233146329284152202253034631822681833788666877215207.
Diese Zahlen finden sich auch in meinem o. g. Posting
vom 02.04.
OK
>>>sqrt(-1) mit Tonelli-Shanks scheint aber schwieriger zu sein.
>>
>>Das entsprechende Legendre-Symbol hat den Wert 1; das sollte
>>dann wohl eigentlich heißen, daß es Quadratwurzeln von -1 gibt.
>>In einer ruhigen Stunde werde ich mal den Tonelli-Shanks-
>>Algorithmus auf -1 anwenden und hoffe, daß dann ein Wert
>>für die Wurzel(n) herauskommt.
>
>Mal sehen, ob das über Ostern klappt.
Ergebnis:
19681161376707505956807079304988542015446066515923890162744021073123829784752
und
38214883241950591754978413199355411911188925816896391856984770930832735035197.
Damit wären schon mal einige Aussagen aus
<https://ybtra.de/div/2023h1/20230330c.png> verifiziert,
und ich habe schon mal einen gewissen Durchblick erlangt.
Sehr schön! :-)
Frohe Ostern,
Marcel
--
╭──────╮ ╭───╮ ╭─╮ ╭───────╮ ..61..╭─╮
╮ ╭─╯ ╭───╯ ╰─╮ ╰────╮ ╭───╯ ╰──────╯ ..52..╰──╮ │ ╰─╮
╰─╯ ╰──╮ ╭──╮ ╭─╮ ╭─╯ │ │ ..52..╭──╯ ╭───╯ ╰─
╰─╯ ╰───╯ ╰─╯ ╰───╯ ╰────╯ ..67..
Marcel Logen
Apr 9, 2023, 8:03:36 AM4/9/23
to
Marcel Logen in de.test:
>Damit wären schon mal einige Aussagen aus
><https://ybtra.de/div/2023h1/20230330c.png> verifiziert,
Jetzt die Montgomery-Kurve
v² = u³ + 486662u² + u
über Fq mit q=2^255-19 (also "Curve25519" von DJB).
Sei also u = 9. Dann ist
v² = 39420360.
Die Wurzeln davon sind:
v = ± 14781619447589544791020593568409986887264606134616475288964881837755586237401
Also
14781619447589544791020593568409986887264606134616475288964881837755586237401
und
43114425171068552920764898935933967039370386198203806730763910166200978582548
Probe:
| user15@o15:~/ybtra-o15$ bc -lq
| scale=0
| (14781619447589544791020593568409986887264606134616475288964881837755586237401^2)%(2^255-19)
| 39420360
|
| (43114425171068552920764898935933967039370386198203806730763910166200978582548^2)%(2^255-19)
| 39420360
| user15@o15:~/ybtra-o15$
Das sind die Zahlen V(P) aus dem RFC und dem korrigierten RFC:
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
<https://www.rfc-editor.org/rfc/inline-errata/rfc7748.html>
Marcel
--
╮ ...4..╭───────╮ ╭─────╮ ╭──────────────────────────╮ ╭────────────
│...2..╭─╯ ╭────╯ │ ╭──╯ ╰────────────────╮ ╭──────╯ ╰──────╮
╰─╮ │ ╭─╯ ╭─╮ ╭─╯ ╰────╮ ╭───╮ ..41..│ ╰─╮ ╭─╮ ╭─╮ ╭──╯
╰────╯ ╰───╯ ╰─╯ ╰──╯ ╰──────────╯ ╰──╯ ╰──╯ ╰─╯ ..67..
>Damit wären schon mal einige Aussagen aus
><https://ybtra.de/div/2023h1/20230330c.png> verifiziert,
v² = u³ + 486662u² + u
über Fq mit q=2^255-19 (also "Curve25519" von DJB).
Sei also u = 9. Dann ist
v² = 39420360.
Die Wurzeln davon sind:
v = ± 14781619447589544791020593568409986887264606134616475288964881837755586237401
Also
14781619447589544791020593568409986887264606134616475288964881837755586237401
und
43114425171068552920764898935933967039370386198203806730763910166200978582548
Probe:
| user15@o15:~/ybtra-o15$ bc -lq
| scale=0
| 39420360
|
| (43114425171068552920764898935933967039370386198203806730763910166200978582548^2)%(2^255-19)
| 39420360
| user15@o15:~/ybtra-o15$
Das sind die Zahlen V(P) aus dem RFC und dem korrigierten RFC:
<https://www.rfc-editor.org/rfc/rfc7748.html#section-4.1>
<https://www.rfc-editor.org/rfc/inline-errata/rfc7748.html>
Marcel
--
╮ ...4..╭───────╮ ╭─────╮ ╭──────────────────────────╮ ╭────────────
│...2..╭─╯ ╭────╯ │ ╭──╯ ╰────────────────╮ ╭──────╯ ╰──────╮
╰─╮ │ ╭─╯ ╭─╮ ╭─╯ ╰────╮ ╭───╮ ..41..│ ╰─╮ ╭─╮ ╭─╮ ╭──╯
╰────╯ ╰───╯ ╰─╯ ╰──╯ ╰──────────╯ ╰──╯ ╰──╯ ╰─╯ ..67..
Marcel Logen
Apr 9, 2023, 8:22:18 AM4/9/23
to
Marcel Logen in de.test:
>Jetzt die Montgomery-Kurve
>
> v² = u³ + 486662u² + u
Hier eine Abbildung:
<https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
Marcel
--
╰───────────────╮ ╭─────────╮ ╭─╮ ╭─╮ ..59..╭───╮ ╭─
│ ╰──╮ ╰─────╯ │ ╭────╯ ╰─╮ ╭───╮..59..╰─╮ │ │
╭──╯ ╭─╮ │ ╭─╯ │ ╰──╯ │..59..╭─╯ ╰─╯
╰─────╯ ╰──╯ ╰───╯ ╰──────╯ ..67..
>Jetzt die Montgomery-Kurve
>
> v² = u³ + 486662u² + u
<https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
Marcel
--
╰───────────────╮ ╭─────────╮ ╭─╮ ╭─╮ ..59..╭───╮ ╭─
│ ╰──╮ ╰─────╯ │ ╭────╯ ╰─╮ ╭───╮..59..╰─╮ │ │
╭──╯ ╭─╮ │ ╭─╯ │ ╰──╯ │..59..╭─╯ ╰─╯
╰─────╯ ╰──╯ ╰───╯ ╰──────╯ ..67..
Marcel Logen
Apr 9, 2023, 11:29:44 AM4/9/23
to
Marcel Logen in de.test:
>>Jetzt die Montgomery-Kurve
>>
>> v² = u³ + 486662u² + u
>
>Hier eine Abbildung:
><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
Ich glaube mittlerweile aber, daß dieses Bild für die
>>Jetzt die Montgomery-Kurve
>>
>> v² = u³ + 486662u² + u
>
>Hier eine Abbildung:
><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
Berechnungen mit Ganzzahlen und modulo wenig oder nicht
geeignet ist.
Marcel
--
╮ ╭────────╮ ╭─╮ ╭─╮ ╭──╮ ..65..╭─
╰─╮ ╰────╮ │ ╭─╮ ╭──╯ ╰─╮ │ ╰─────╮ ╭────╯ │ ╭─╮ ..63..╭─╯
│ ╭────╯ ╰─╯ ╰───╯ ╭───╯ ╰───╮ ╰─╯ ╭────╯ ╭──╯ │ ╭──╮ ╭─╯
╰──╯ ╰──────────╯ ..40..╰──────╯ ╰───╯ ╰─╯
Marcel Logen
Apr 9, 2023, 12:41:52 PM4/9/23
to
Marcel Logen in de.test:
>>>Jetzt die Montgomery-Kurve
>>>
>>> v² = u³ + 486662u² + u
>>
>>Hier eine Abbildung:
>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>
>Ich glaube mittlerweile aber, daß dieses Bild für die
>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>geeignet ist.
Mit reellen Zahlen ergibt sich für den linken Endpunkt die
>>>Jetzt die Montgomery-Kurve
>>>
>>> v² = u³ + 486662u² + u
>>
>>Hier eine Abbildung:
>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>
>Ich glaube mittlerweile aber, daß dieses Bild für die
>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>geeignet ist.
u-Koordinate (waagerechte Achse):
-486661.999997945185775745338116606188097906388169088898287950144743\
51530636128998671931575275443955756739454936990847857570179064693656\
93142056836957636473283206988124237414982998436769025860002257610236\
66006373128839329292160441417849931136144469791759567344372337595049\
54325759769815725803352689511738367291471408083929523335345193892982\
39588904140789439468324846013248556456116198560189777806123690244244\
24039344146409242740279890154693173637845393130504822725701818506878\
83432070412739381944694630369875903588711835961092558521241285612852\
38206223320365122780424607807072657820155473219568161440669737984121\
20569318308619937466536217468185256332309905070403088761326018591807\
30873986003261013202784529352691541094285925183206842036322062391282\
68218288339273314414186098017677941479435275862538793838631356477438\
34167183994054511876032245897776220075199235940461262630666038390215\
12826954459616732066265034664749593623563224810929773403360615776343\
73886250622326982324417123172478923886473785413003196057903649971719\
70025894530129095200659619895552805066623875912282218938445734627283\
67800632916955695617405207429230296454182042754892933151978924819637\
81717325424689536177113440144954280569758244733531869644969516390457\
47018221040067203792830531735576471136932900409130692217641038276914\
03519608744929217348756114634099624252972156737760582222577268237965\
89222376192530565550769453229969463821801999747930368434244808088221\
02483861070388369283286732752162281366999766751636175998854930725968\
79794454132351989674528313112151614990684688760447422552093102368690\
41561577480125561436301662571862673275413723835415757795918131952472\
26714431082834695915858138123038046880470929559162814524652719156313\
78332200292002039535370447560942820694056708512650556282361423717585\
8984365036967282473150129209206655196950
also *fast* -486662.
Marcel
--
─╮ ╭───────╮ ╭─────────╮ ╭─────────────╮ ╭───╮ ╭─╮ ..66..│
╰─╯ ╭───╯ ╰──────╮ │ ╰───────────╮ ╰───╮ │ ╰───╯ ╰─╮ ..66..│
╭─────╯ ╭─╮ ╭─╮ ╭──╯ ╰──╮ ╰───╮ │ ╰─╮..54..╭──╯ ╭───╮ │
╰─────────╯ ╰─╯ ╰──╯ ╰───────────────╯ ╰────╯..54..╰────╯ ╰──╯
Marcel Logen
Apr 9, 2023, 12:43:05 PM4/9/23
to
Marcel Logen in de.test:
>>>Jetzt die Montgomery-Kurve
>>>
>>> v² = u³ + 486662u² + u
>>
>>Hier eine Abbildung:
>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>
>Ich glaube mittlerweile aber, daß dieses Bild für die
>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>geeignet ist.
>>>Jetzt die Montgomery-Kurve
>>>
>>> v² = u³ + 486662u² + u
>>
>>Hier eine Abbildung:
>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>
>Ich glaube mittlerweile aber, daß dieses Bild für die
>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>geeignet ist.
Marcel
[supersedes]
--
╭─────╮ ╭──────╮ ╭───────────╮ ..52..╭─────╮ ╭────╮
│ ╭──╯ ╰───╮ │ ╰────────╮ ╰───╮ ..45..╭───╮ ╰─╮ ╰─╯ ╭─╯
─╯ ╰────╮ ╭──╮ │ │ ╭──╮ ╭───╯ ╰─╮ ╭─╮ ╰─╮ ╰────╯ ..63..│
╰─╯ ╰────╯ ╰─╯ ╰──╯ ╰─╯ ╰────╯ ..63..╰───
Marcel Logen
Apr 9, 2023, 12:45:45 PM4/9/23
to
Marcel Logen in de.test:
>>>>Jetzt die Montgomery-Kurve
>>>>
>>>> v² = u³ + 486662u² + u
>>>
>>>Hier eine Abbildung:
>>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>>
>>Ich glaube mittlerweile aber, daß dieses Bild für die
>>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>>geeignet ist.
>
>Mit reellen Zahlen ergibt sich für den linken Endpunkt die
>u-Koordinate (waagerechte Achse):
>
>-486661.999997945185775745338116606188097906388169088898287950144743\
>51530636128998671931575275443955756739454936990847857570179064693656\
[...]
>>>>Jetzt die Montgomery-Kurve
>>>>
>>>> v² = u³ + 486662u² + u
>>>
>>>Hier eine Abbildung:
>>><https://de.wikipedia.org/wiki/Curve25519#/media/Datei:Curve25519.png>
>>
>>Ich glaube mittlerweile aber, daß dieses Bild für die
>>Berechnungen mit Ganzzahlen und modulo wenig oder nicht
>>geeignet ist.
>
>Mit reellen Zahlen ergibt sich für den linken Endpunkt die
>u-Koordinate (waagerechte Achse):
>
>-486661.999997945185775745338116606188097906388169088898287950144743\
>51530636128998671931575275443955756739454936990847857570179064693656\
>also *fast* -486662.
>
>u = -sqrt(59209975560)-243331
| u
| -486661.99999794518577574533
Marcel
--
╭───────╮ ╭──────╮ ╭──────────────╮ ╭─╮ ..63..╭──╮
╰─────╮ │ │ ╰─────────╯ ..43..╰─╮ │ ╰─╮ ╭───╯ ╰
╮ ╭─╮ │ ╰─╮ ╭──╯ ╭──╯ ╭─╯ ╰───╯ ..67..
╰─╯ ╰──╯ ╰─╯ ╰──────╯ ..67..
0 new messages