{"id":1297,"date":"2018-06-26T04:04:42","date_gmt":"2018-06-26T03:04:42","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=1297"},"modified":"2018-07-02T09:45:58","modified_gmt":"2018-07-02T08:45:58","slug":"numeri-pseudocasuali-e-il-ritorno-dei-trng","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2018\/06\/26\/numeri-pseudocasuali-e-il-ritorno-dei-trng\/","title":{"rendered":"Numeri pseudocasuali e il ritorno dei TRNG"},"content":{"rendered":"

Abbiamo visto la volta scorsa<\/a> che gli scienziati hanno bisogno di tanti numeri casuali, ma gli informatici hanno bisogno che i programmi abbiano sempre gli stessi dati di input per poterli testare. La soluzione che si \u00e8 scelta \u00e8 stata quella dei generatori di numeri pseudocasuali, i PRNG. Un PNRG \u00e8 in pratica una funzione matematica deterministica che viene man mano iterata, nel senso che usa il risultato precedente per calcolare quello nuovo. Quindi se si parte con dallo stesso valore iniziale (il “seme”, in inglese \u201cseed\u201d) si otterr\u00e0 sempre la stessa soluzione. Il problema a questo punto si sposta: bisogna dimostrare che le successioni ottenute siano effettivamente abbastanza casuali per gli scopi previsti, e che questo capiti con qualunque seme.<\/p>\n

\"\"
Sar\u00e0 davvero casuale? di Firkin, da https:\/\/openclipart.org\/detail\/224695\/<\/figcaption><\/figure>\n

La prima persona a sviluppare un PNRG fu John von Neumann, nel 1946. La sua idea fu di partire da un seme iniziale, elevarlo al quadrato e prendere le cifre di mezzo del risultato. Peccato che all’atto pratico si arrivi sempre a un ciclo molto breve, come 8100, 6100, 4100, 8100, 6100, 4100, \u2026 che di casuale ha davvero ben poco. Intendiamoci: una qualunque funzione deterministica produrr\u00e0 un ciclo, di qui non si scappa. Ma se il ciclo \u00e8 moooolto grande, lungo miliardi di miliardi, \u00e8 poi cos\u00ec importante? Evidentemente no. Tutto stava insomma nel cercare una formula relativamente semplice da implementare, o meglio che sputasse il nuovo valore pseudocasuale molto in fretta, e che avesse un ciclo molto lungo di ripetizioni. Ah: dimenticavo che naturalmente la formula deve anche dare numeri sufficientemente casuali. Pensate a che cosa succederebbe se la cifra 9 comparisse la met\u00e0 delle volte rispetto all’8!<\/p>\n

La prima formula di questo tipo usata in pratica fu definita nel 1949 dal matematico D. H. Lehmer – magari ne avete sentito parlare a proposito dei primi di Mersenne, visto che ha modificato il criterio di Lucas per renderlo ancora pi\u00f9 veloce – con i generatori a congruenze lineari (linear congruential generators, o LCG in breve). L’idea alla base di un LCG \u00e8 scegliere opportunamente tre numeri positivi a, b, m: una volta poi preso un valore di partenza r<\/em>, quello successivo sar\u00e0 s<\/em> = ar<\/em>+b<\/em> mod m<\/em>. \u00c8 immediato vedere che il ciclo di questo generatore \u00e8 al pi\u00f9 lungo m; in realt\u00e0 a seconda dei valori di a<\/em> e b<\/em> esso potrebbe essere un suo divisore. Quello che succede in pratica \u00e8 che si sceglie spesso m<\/em> come 232<\/sup> oppure 264<\/sup>, perch\u00e9 sono numeri comodi per velocizzare le operazioni; poich\u00e9 per\u00f2 non sono i migliori per la generazione di numeri davvero casuali e soprattutto di successioni<\/i> di numeri casuali, vengono mostrati solo i bit pi\u00f9 significativi del risultato.<\/p>\n

Se vi sembra che tutti questi caveat siano solo fisime dei matematici, sbagliate di grosso. Tanto per dire, a met\u00e0 anni ’90 venne scoperto un problema con i certificati SSL di Netscape, quelli che servono per le connessioni protette con il protocollo https. In pratica, Netscape – che all’epoca era tra i pi\u00fa importanti attori – usava come seme per il suo LCG una combinazione del tempo di sistema e del numero di processo, il che significava che un cracker poteva facilmente ricavare quei dati e decrittare tutti i dati della sessione che a questo punto era tutto meno che sicura. Si doveva insomma tornare a qualche altro sistema davvero casuale, almeno per quando i programmi erano ormai stati testati e dovevano essere eseguiti in pratica. Alla fine degli anni ’90 ci sono stati due esempi pratici: dalla SGI LavaRand, che generava numeri casuali filmando una coppia di lava lamp (ve l’avevo detto che l’idea era molto anni ’90) e generando 165Kb\/s di dati casuali; da uno dei fondatori di Autodesk invece nacque HotBits, che sfruttava un contatore geiger per ottenere numeri quantisticamente casuali. Nel 1998 \u00e8 stato anche creato il sito irlandese random.org<\/a>, che oggi fornisce Numeri Davvero Casuali con servizi gratuiti e a pagamento. Nel 1999 infine l’Intel ha cominciato a introdurre nei chipset i810 un generatore di numeri casuali basato sul rumore termico, anche se un po’ pi\u00f9 lento di quelli software; se quindi vogliamo comunque usare un PNRG esiste un bellissimo software del 1997, sviluppate da Makoto Matsumoto (\u677e\u672c \u771e) e Takuji Nishimura (\u897f\u6751 \u62d3\u58eb). Il Mersenne Twister<\/a> si chiama cos\u00ec perch\u00e9 usa come base un primo di Mersenne. Quello usato attualmente ha un ciclo di lunghezza 219937<\/sup>−1, che dovrebbe essere sufficiente per un qualunque uso pratico.<\/p>\n

E nel nuovo millennio? Si \u00e8 partiti a studiare i PNRG crittograficamente sicuri (CSPRNG) e i TRNG open source per sincerarci che i valori forniti non abbiano qualche backdoor inserita dalla NSA. Ma su questo vi rimando all’articolo di FreeCodeCamp<\/a> da cui ho preso molte delle informazioni di questi post. Buona lettura :)<\/p>\n","protected":false},"excerpt":{"rendered":"

Qualche rapida informazione sui generatori di numeri pseudocasuali<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[193],"class_list":["post-1297","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-numeri-casuali"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-kV","jetpack-related-posts":[{"id":2470,"url":"https:\/\/xmau.com\/ilpost\/2012\/01\/09\/sudoku-minimali-e-massimali\/","url_meta":{"origin":1297,"position":0},"title":"Sudoku minimali e massimali","author":".mau.","date":"09\/01\/2012","format":false,"excerpt":"Il 2012 si \u00e8 aperto con la dimostrazione che per avere un sudoku risolvibile \u00e8 necessario avere almeno 17 numeri. Come ci si \u00e8 arrivati? Forza (quasi) bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2012\/01\/sudoku77.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1450,"url":"https:\/\/xmau.com\/ilpost\/2019\/03\/19\/percentuali-troppo-precise-pillole\/","url_meta":{"origin":1297,"position":1},"title":"Percentuali particolarmente precise [Pillole]","author":".mau.","date":"19\/03\/2019","format":false,"excerpt":"Quando si vogliono creare dati mancanti, forse \u00e8 meglio pensarci su un attimo e studiare il modo migliore per farlo.","rel":"","context":"In \"matematica nella vita reale\"","block_context":{"text":"matematica nella vita reale","link":"https:\/\/xmau.com\/ilpost\/tag\/matematica-nella-vita-reale\/"},"img":{"alt_text":"il tweet di Democratica","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/percentuali.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/percentuali.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/percentuali.png?resize=525%2C300 1.5x"},"classes":[]},{"id":2598,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/26\/parilandia\/","url_meta":{"origin":1297,"position":2},"title":"Parilandia","author":".mau.","date":"26\/04\/2013","format":false,"excerpt":"Noi diamo per scontata la fattorizzazione unica, ma non \u00e8 sempre cos\u00ec.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1503,"url":"https:\/\/xmau.com\/ilpost\/2019\/07\/10\/numeri-felici\/","url_meta":{"origin":1297,"position":3},"title":"Numeri felici","author":".mau.","date":"10\/07\/2019","format":false,"excerpt":"una categoria di numeri con propriet\u00e0 facili da studiare... ma non troppo.","rel":"","context":"In \"didattica della matematica\"","block_context":{"text":"didattica della matematica","link":"https:\/\/xmau.com\/ilpost\/tag\/didattica-della-matematica\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/happynumbers.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":444,"url":"https:\/\/xmau.com\/ilpost\/2014\/10\/31\/aritmetica-di-robinson\/","url_meta":{"origin":1297,"position":4},"title":"Aritmetica di Robinson","author":".mau.","date":"31\/10\/2014","format":false,"excerpt":"I teoremi di G\u00f6del vi sembrano troppo complicati? Eccovi un modo molto semplice per trovare una proposizione indecidibile secondo certe regole aritmetiche.","rel":"","context":"In \"assiomi\"","block_context":{"text":"assiomi","link":"https:\/\/xmau.com\/ilpost\/tag\/assiomi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1499,"url":"https:\/\/xmau.com\/ilpost\/2019\/06\/27\/recensione-matematica-per-giovani-menti\/","url_meta":{"origin":1297,"position":5},"title":"Recensione: Matematica per giovani menti","author":".mau.","date":"27\/06\/2019","format":false,"excerpt":"Settantacinque problemi matematici e logici pensati per chi la matematica se la trova davanti pi\u00f9 di quanto vorrebbe.","rel":"","context":"In \"libri\"","block_context":{"text":"libri","link":"https:\/\/xmau.com\/ilpost\/tag\/libri\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/06\/9788822068842.jpg?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1297","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=1297"}],"version-history":[{"count":5,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1297\/revisions"}],"predecessor-version":[{"id":1304,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1297\/revisions\/1304"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=1297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=1297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=1297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}