🚀 go-pugleaf

jest https://en.wikipedia.org/wiki/Blum_Blum_Shub
i https://en.wikipedia.org/wiki/Blum%E2%80%93Micali_algorithm

trzeba by użyć GMP
jakiej wielkości powinny być współczynniki aby wygenerować np. 256 
bitowe liczby?

On Sunday, January 5, 2020 at 4:00:50 PM UTC+1, Borneq wrote:
> jest https://en.wikipedia.org/wiki/Blum_Blum_Shub
> i https://en.wikipedia.org/wiki/Blum%E2%80%93Micali_algorithm
> 
> trzeba by użyć GMP
> jakiej wielkości powinny być współczynniki aby wygenerować np. 256 
> bitowe liczby?


Nie wiem. To jest generator do zastosowań kryptograficznych. W  takich
zastosowaniach chyba warto wziąć bardzo duże p i q, a następnie 
przeskakiwać wiele (miliardy?) wygenerowanych liczb?


Ja skupiłem się na testach tylko niektórych generatorów i na ich 
rozbudowanych wersjach:

1) Fibonacciego:
  return ( x[i] = ( x[i-N] * A + x[i-M] * B + C ) % M ) / D

2) Podobne do liniowych:
  return ( x = x * A + B ) % M ) / D

3) Wyhash ( ogólniej: dodawanie i funkcja skrótu )  
  return hash( x = x + A );

4) Biblioteczne:
 - RANLUX_48
 - MT19937_64

Pozdrawiam

W dniu 2020-01-07 o 11:15, M.M. pisze:

> Ja skupiłem się na testach tylko niektórych generatorów i na ich
> rozbudowanych wersjach:

Mógłbyś kilka słów jaki jest cel testów.
Chodzi o szybkość działania, czy chcesz wyłapać jakieś niedoskonałości 
generatorów.
Nie jestem programistą - nie wczytywałem się w kody generatorów ani testów.

Ja sobie napisałem generator inspirując się opisem z książki: Ferguson, 
Schneier "Kryptografia w praktyce". Wydaje mi się (dawno było), że tak 
totalnie to uprościłem (szczególnie gromadzenie entropii), że może nawet 
nie powinienem pisać 'inspirując się'.
Mój generator oparty jest na funkcji SHA512d.
Literka d oznacza SHA512(SHA512(dane)) bo autorzy nie do końca ufają 
funkcjom SHA i nie znając się postanowiłem po prostu przyjąć ich racje.
Szybkości działania mnie w ogóle nie interesowała.
P.G.

On Tuesday, January 7, 2020 at 1:11:08 PM UTC+1, Piotr Gałka wrote:
> W dniu 2020-01-07 o 11:15, M.M. pisze:
> 
> > Ja skupiłem się na testach tylko niektórych generatorów i na ich
> > rozbudowanych wersjach:
> 
> Mógłbyś kilka słów jaki jest cel testów.

Czasami jestem między młotem a kowadłem. Gdy używam dobrego generatora, to
część mocy obliczeniowej idzie na generowanie liczb losowych. Gdy używam
szybkiego, to boję się, się losowość liczb jest zbyt słaba do rozwiązywania
problemów przy pomocy algorytmów ewolucyjnych, symulowanego wyżarzania, itd.

Chciałbym mieć bardzo szybki algorytm o niskim ryzyku że zadanie zostanie
gorzej rozwiązane z powodu słabej jakości liczb losowych - w sumie to 
jest mój główny cel. Zrobiłem jednolity interfejs żeby łatwo (bez
ryzyka uszkodzenia generatora) przełączać się pomiędzy generatorami i
porównywać je w testach. 

Wcześniej myślałem że generatory Fibonacciego spełniają zarówno wymagania
szybkości jak i jakości generowanych liczb. Doskonale przechodziły testy w
programie dieharder, a Mersenne Twister nie przechodził i działał wyraźnie
wolniej. Jednak w programie PractRand wyniki testów dla generatorów
Fibonacciego zazwyczaj były kiepskie - to ostatecznie przechyliło szalę 
żeby zrobić kilka eksperymentów z różnymi generatorami. 


> Chodzi o szybkość działania, czy chcesz wyłapać jakieś niedoskonałości 
> generatorów.

Chcę przede wszystkim mieć dużą kontrolę nad jakością generowanych liczb 
przy maksymalnej wydajności. Gdy jakość generowanych liczb nie musi być
wysoka, ale szybkość generowania jest ważna, to chcę wiedzieć czy nie
mam błędów z powodu agresywnej optymalizacji i chcę wiedzieć jak spada
jakość generowanych liczb w testach: do tego celu mam parametryzowalne 
adaptery: add-rot, xor, rndbuf, rndfbuf. Adaptery też można wrzucić do
testów i sprawdzić jak szybko działają i jak spadają wyniki w testach.
Przyznać jednak muszę, że przy tak wydajnym generatorze jak wyhash64 
używanie niektórych adapterów może okazać się bezcelowe. 

Jeśli z użyciem tego kodu napisze się odpowiednio program, to można
potem wygodnie zrobić szereg kolejnych testów. Wystarczy sterować warunkową
kompilacją (identycznie jak w testach samych generatorów) i widać jak na 
dłoni czy jakość rozwiązania spada, czy czas obliczeń rośnie. Jeśli czas
obliczeń nie spada po użyciu adapterów, to można je bezpiecznie wyłączyć
kompilacją warunkową bez ingerencji w kod. 


> Nie jestem programistą - nie wczytywałem się w kody generatorów ani testów.
> 
> Ja sobie napisałem generator inspirując się opisem z książki: Ferguson, 
> Schneier "Kryptografia w praktyce". Wydaje mi się (dawno było), że tak 
> totalnie to uprościłem (szczególnie gromadzenie entropii), że może nawet 
> nie powinienem pisać 'inspirując się'.
> Mój generator oparty jest na funkcji SHA512d.
> Literka d oznacza SHA512(SHA512(dane)) bo autorzy nie do końca ufają 

Moje udoskonalenie(?) wyhash mniej-więcej na tym:

if( i1 >= size(dane1) ) i1 = 0;
dane1[ i1 ] += liczba_pierwsza1;

if( i2 >= size(dane2) ) i2 = 0;
dane2[ i2 ] += liczba_pierwsza2;

DANE = dane1[i1] ^ dane2[i2];
i1 = i1 + 1;
i2 = i2 + 1;

return hash( DANE );


> funkcjom SHA i nie znając się postanowiłem po prostu przyjąć ich racje.
> Szybkości działania mnie w ogóle nie interesowała.

Niektóre moje programy wyraźnie przyspieszają po zmianie generatora na
szybszy. Dlatego mnie bardzo interesuje szybkość generowanych liczb. Gdyby
mnie nie interesowała to bym wziął ranlux48. Zresztą mój kod jak najbardziej
umożliwia użycie standardowego ranluxa48 i Mersenne Twister. Standardowego
Knutha i ministd zakomentowałem bo zawieszały diehardera i dawały same 
faile w programie PractRand ;-)


Pozdrawiam

W dniu 2020-01-07 o 15:23, M.M. pisze:

Dzięki za odpowiedź.
Nie jest dla mnie wielkim pożytkiem, ale zaspokaja ciekawość.

> Moje udoskonalenie(?) wyhash mniej-więcej na tym:
> 
> if( i1 >= size(dane1) ) i1 = 0;
> dane1[ i1 ] += liczba_pierwsza1;
> 
> if( i2 >= size(dane2) ) i2 = 0;
> dane2[ i2 ] += liczba_pierwsza2;
> 
> DANE = dane1[i1] ^ dane2[i2];
> i1 = i1 + 1;
> i2 = i2 + 1;
> 
> return hash( DANE );

Jeśli wszystko rusza 'od zera' to kolejne wyniki aż do przepełnienia 
jednego z liczników będą takie same: DANE = Lp1^Lp2,
A potem znów seria takich samych danych: DANE = (2*L1)^L2,

Zapewne nie rusza 'od zera', ale w ramach 'dmuchania na zimne' 
próbowałbym unikać takiej możliwości.

>> funkcjom SHA i nie znając się postanowiłem po prostu przyjąć ich racje.
>> Szybkości działania mnie w ogóle nie interesowała.
> 
> Niektóre moje programy wyraźnie przyspieszają po zmianie generatora na
> szybszy. Dlatego mnie bardzo interesuje szybkość generowanych liczb. Gdyby
> mnie nie interesowała to bym wziął ranlux48. Zresztą mój kod jak najbardziej
> umożliwia użycie standardowego ranluxa48 i Mersenne Twister. Standardowego
> Knutha i ministd zakomentowałem bo zawieszały diehardera i dawały same
> faile w programie PractRand ;-)

To niestety poza 'domyślaniem się' nic mi nie mówi, ale to mój problem.
Nigdy nie użyłem żadnego innego kodu, niż to co mam z definicji w 
Builderze i to co sam napisałem (jak. AES, SHA, ...).
Programowanie w moim przypadku to tydzień dwa w roku.
P.G.

On Tuesday, January 7, 2020 at 6:15:44 PM UTC+1, Piotr Gałka wrote:
> W dniu 2020-01-07 o 15:23, M.M. pisze:
> 
> Dzięki za odpowiedź.
> Nie jest dla mnie wielkim pożytkiem, ale zaspokaja ciekawość.
> 
> > Moje udoskonalenie(?) wyhash mniej-więcej na tym:
> > 
> > if( i1 >= size(dane1) ) i1 = 0;
> > dane1[ i1 ] += liczba_pierwsza1;
> > 
> > if( i2 >= size(dane2) ) i2 = 0;
> > dane2[ i2 ] += liczba_pierwsza2;
> > 
> > DANE = dane1[i1] ^ dane2[i2];
> > i1 = i1 + 1;
> > i2 = i2 + 1;
> > 
> > return hash( DANE );
> 
> Jeśli wszystko rusza 'od zera' to kolejne wyniki aż do przepełnienia 
> jednego z liczników będą takie same: DANE = Lp1^Lp2,
> A potem znów seria takich samych danych: DANE = (2*L1)^L2,
> 
> Zapewne nie rusza 'od zera', ale w ramach 'dmuchania na zimne' 
> próbowałbym unikać takiej możliwości.

Tak, unikam, tablica na początku powinna zawierać chaotyczne i unikalne 
dane. Inicjuję wszelkie tablice (także w generatorze Fibonacciego)
tą funkcją:
https://github.com/mmarszik/MRndCPP/blob/master/init_chaos.h

> 
> >> funkcjom SHA i nie znając się postanowiłem po prostu przyjąć ich racje.
> >> Szybkości działania mnie w ogóle nie interesowała.
> > 
> > Niektóre moje programy wyraźnie przyspieszają po zmianie generatora na
> > szybszy. Dlatego mnie bardzo interesuje szybkość generowanych liczb. Gdyby
> > mnie nie interesowała to bym wziął ranlux48. Zresztą mój kod jak najbardziej
> > umożliwia użycie standardowego ranluxa48 i Mersenne Twister. Standardowego
> > Knutha i ministd zakomentowałem bo zawieszały diehardera i dawały same
> > faile w programie PractRand ;-)
> 
> To niestety poza 'domyślaniem się' nic mi nie mówi, ale to mój problem.
> Nigdy nie użyłem żadnego innego kodu, niż to co mam z definicji w 
> Builderze i to co sam napisałem (jak. AES, SHA, ...).
> Programowanie w moim przypadku to tydzień dwa w roku.
> P.G.

On Wednesday, January 8, 2020 at 12:22:05 PM UTC+1, M.M. wrote:
> On Tuesday, January 7, 2020 at 6:15:44 PM UTC+1, Piotr Gałka wrote:
> > W dniu 2020-01-07 o 15:23, M.M. pisze:
> > 
> > Dzięki za odpowiedź.
> > Nie jest dla mnie wielkim pożytkiem, ale zaspokaja ciekawość.
> > 
> > > Moje udoskonalenie(?) wyhash mniej-więcej na tym:
> > > 
> > > if( i1 >= size(dane1) ) i1 = 0;
> > > dane1[ i1 ] += liczba_pierwsza1;
> > > 
> > > if( i2 >= size(dane2) ) i2 = 0;
> > > dane2[ i2 ] += liczba_pierwsza2;
> > > 
> > > DANE = dane1[i1] ^ dane2[i2];
> > > i1 = i1 + 1;
> > > i2 = i2 + 1;
> > > 
> > > return hash( DANE );
> > 
> > Jeśli wszystko rusza 'od zera' to kolejne wyniki aż do przepełnienia 
> > jednego z liczników będą takie same: DANE = Lp1^Lp2,
> > A potem znów seria takich samych danych: DANE = (2*L1)^L2,
> > 
> > Zapewne nie rusza 'od zera', ale w ramach 'dmuchania na zimne' 
> > próbowałbym unikać takiej możliwości.
> 
> Tak, unikam, tablica na początku powinna zawierać chaotyczne i unikalne 
> dane. Inicjuję wszelkie tablice (także w generatorze Fibonacciego)
> tą funkcją:
> https://github.com/mmarszik/MRndCPP/blob/master/init_chaos.h
> 
> > 
> > >> funkcjom SHA i nie znając się postanowiłem po prostu przyjąć ich racje.
> > >> Szybkości działania mnie w ogóle nie interesowała.
> > > 
> > > Niektóre moje programy wyraźnie przyspieszają po zmianie generatora na
> > > szybszy. Dlatego mnie bardzo interesuje szybkość generowanych liczb. Gdyby
> > > mnie nie interesowała to bym wziął ranlux48. Zresztą mój kod jak najbardziej
> > > umożliwia użycie standardowego ranluxa48 i Mersenne Twister. Standardowego
> > > Knutha i ministd zakomentowałem bo zawieszały diehardera i dawały same
> > > faile w programie PractRand ;-)
> > 
> > To niestety poza 'domyślaniem się' nic mi nie mówi, ale to mój problem.
> > Nigdy nie użyłem żadnego innego kodu, niż to co mam z definicji w 
> > Builderze i to co sam napisałem (jak. AES, SHA, ...).
> > Programowanie w moim przypadku to tydzień dwa w roku.
> > P.G.

Kontynuując:

Generator Mersenne T. w wersji 64bitowej nie przeszechodzi testów w programie PractRand nawet jak się bierze z niego tylko 32 bity. Padł po 260 minutach:

https://github.com/mmarszik/MRndCPP/blob/master/use_rnd_mt19937_64.h

---------------------------------------------------------------------

Kombinacja 16 generatorów na typie uint128 według wzoru:
r = random() % 16;
return (x[r] = x[r] * A[r] + B[r]) >> 95
Przechodzi cztero-dobowe testy:
https://github.com/mmarszik/MRndCPP/blob/master/use_rnd_mlin_0.h

Wygenerowała w testach 11.339 terabytes danych.

---------------------------------------------------------------------

Generator wyhash64 przechodzi cztery doby testów:
https://github.com/mmarszik/MRndCPP/blob/master/use_rnd_wyhash64_0.h

Wygenerował w tym czasie length= 11.544 terabytes danych.

---------------------------------------------------------------------

Moja rozbudowa wyhash też przeszła 4 doby testów:

https://github.com/mmarszik/MRndCPP/blob/master/use_rnd_wyhash64m_0.h

Niestety jest wolniejsza niż oryginał, wygenerowała 
11.238 terabytes danych


---------------------------------------------------------------------

Wartości typu p=1-3.4e-3, a nawet p=1-3.5e-5 zdarzają się, ale takie
wartości PractRand domyślnie uznaje za dopuszczalne.

Pozdrawiam