Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893
{"id":36922,"date":"2023-07-17T21:58:18","date_gmt":"2023-07-17T21:58:18","guid":{"rendered":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/"},"modified":"2023-07-17T21:58:19","modified_gmt":"2023-07-17T21:58:19","slug":"how-to-build-a-big-prime-number","status":"publish","type":"post","link":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/","title":{"rendered":"How to Build a Big Prime Number"},"content":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/how-to-build-a-big-prime-number-20230713\/#comments<\/a><\/br>
\nHow to Build a Big Prime Number<\/br>
\n2023-07-17 21:58:18<\/br><\/p>\n

\n

Over time, researchers developed the aforementioned approaches. The simplest way is just to guess. If you want a prime with 1,000 digits, for example, you could pick a 1,000-digit number at random and then check it. \u201cIf it\u2019s not prime, you just try another one, and another, and so on until you find one,\u201d said Rahul Santhanam<\/a>, a computer scientist at the University of Oxford and co-author of the new paper. \u201cBecause there are many primes, this algorithm will give you some number that\u2019s prime with a high probability, after a relatively small number of iterations.\u201d But using randomness means you\u2019ll likely get a different number every time, he said. That could be a problem if you need consistency \u2014 if, say, you\u2019re employing a cryptographic method of security that depends on the availability of large primes.<\/p>\n

The other approach is to go with a deterministic algorithm. You could pick a starting point and start testing numbers, sequentially, for primality. Eventually you\u2019re destined to find one, and your algorithm will consistently output the first one you find. But it could take a while: If you\u2019re looking for a prime number with 1,000 digits, even a calculation with 2500<\/sup> steps \u2014 which would take much longer than the age of the universe \u2014 isn\u2019t enough to guarantee success.<\/p>\n

In 2009, the mathematician and Fields medalist Terence Tao wanted to do better. He challenged mathematicians to come up with a deterministic algorithm for finding a prime of a given size within a computational time limit.<\/p>\n

That time limit is known as polynomial time. An algorithm solves a problem in polynomial time if the number of steps it takes is no more than a polynomial function of n<\/em>, the size of the input. (A polynomial function includes terms that have variables raised to positive integer powers, like n<\/em>2<\/sup> or 4n<\/em>3<\/sup>.) In the context of prime number construction, n<\/em> refers to the number of digits in the prime you want. Computationally speaking, this doesn\u2019t cost much: Computer scientists describe problems that can be solved by algorithms in polynomial time as easy. A hard problem, by contrast, takes exponential time, which means it requires a number of steps approximated by an exponential function (which includes terms such as 2n<\/sup><\/em>).<\/p>\n

For decades, researchers have investigated the connection between randomness and hardness. The prime number construction problem was considered easy if you allowed randomness \u2014 and were satisfied with receiving a different number each time \u2014 and hard if you insisted on determinism.<\/p>\n

No one has managed to meet Tao\u2019s challenge yet, but the new work comes close. It draws heavily on an approach introduced in 2011 by Shafi Goldwasser and Eran Gat, computer scientists at the Massachusetts Institute of Technology. They described \u201cpseudodeterministic\u201d algorithms \u2014 mathematical recipes for search problems, like finding big primes, that could harness the benefits of randomness and, with high probability, still produce the same answer every time. They would use the efficiency of random bits in the recipe, which would be de-randomized in the outcome, appearing deterministic.<\/p>\n

Researchers have been exploring pseudodeterministic algorithms ever since. In 2017, Santhanam and Igor Oliveira of the University of Warwick (who also contributed to the new work) described<\/a> a pseudodeterministic approach to constructing primes that used randomness and looked convincingly deterministic, but it worked in \u201csubexponential\u201d time \u2014 faster than exponential, but slower than polynomial time. Then in 2021, Tell and Lijie Chen<\/a>, a computer scientist at the University of California, Berkeley, explored<\/a> how to use a hard problem to build a pseudorandom number generator (an algorithm that generates a string of numbers indistinguishable from a random output). \u201c[We] found a new connection between hardness and pseudorandomness,\u201d Chen said.<\/p>\n

The pieces finally came together in the spring of 2023, during a bootcamp on computational complexity<\/a> at the Simons Institute for the Theory of Computing at Berkeley, when the researchers began to work together on the problem, weaving together past results. For the new work, Chen said, Hanlin Ren \u2014 a computer scientist at Oxford and a co-author \u2014 had the initial ideas to combine the\u00a0Chen-Tell result with the Santhanam-Oliveira approach in a novel way. Then the whole team developed the ideas more fully to produce the new paper.<\/p>\n

The resulting pseudodeterministic algorithm, Santhanam said, used new ways of looking at past work to produce prime numbers in polynomial time. It provably used randomness to output a prime number of a specific length, and the tool is more accurate than random guessing and more computationally efficient than deterministic crunching.<\/p>\n

The new algorithm is also remarkably simple, Santhanam said, and it can be applied to a wide range of search problems \u2014 really, to any dense subset of numbers, like the primes, for which membership can be determined in polynomial time. But it\u2019s not perfect. The algorithm works for infinitely many input lengths, but it doesn\u2019t cover all lengths of digits. There may still be some values of n<\/em> out there for which the algorithm doesn\u2019t deterministically produce a prime.<\/p>\n

\u201cIt would be cool to get rid of that small caveat,\u201d Grossman said.<\/p>\n

The ultimate goal, Santhanam said, is to find an algorithm that doesn\u2019t require randomness at all. But that quest remains open. \u201cDeterminism is what we\u2019d like to use,\u201d he said.<\/p>\n

But he also pointed out that pseudorandom processes are powerful tools, and projects like constructing primes are just one way of using them to connect ideas from mathematics, computer science, information theory and other areas.<\/p>\n

\u201cIt\u2019s exciting to try and think where else these brilliant observations will lead,\u201d Tell said.<\/p>\n<\/div>\n

<\/br><\/br><\/br><\/p>\n

Uncategorized<\/br>
\n<\/br>
\nSource:https:\/\/www.quantamagazine.org\/how-to-build-a-big-prime-number-20230713\/#comments<\/a><\/br><\/br><\/p>\n","protected":false},"excerpt":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/how-to-build-a-big-prime-number-20230713\/#comments How to Build a Big Prime Number 2023-07-17 21:58:18 Over time, researchers developed the aforementioned approaches. The simplest way is just to guess. If you want a prime with 1,000 digits, for example, you could pick a 1,000-digit number at random and then check it. \u201cIf it\u2019s not prime, you just try another one, […]<\/p>\n","protected":false},"author":1,"featured_media":36923,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"pagelayer_contact_templates":[],"_pagelayer_content":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-36922","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"yoast_head":"\nHow to Build a Big Prime Number - Science and Nerds<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"How to Build a Big Prime Number - Science and Nerds\" \/>\n<meta property=\"og:description\" content=\"Source:https:\/\/www.quantamagazine.org\/how-to-build-a-big-prime-number-20230713\/#comments How to Build a Big Prime Number 2023-07-17 21:58:18 Over time, researchers developed the aforementioned approaches. The simplest way is just to guess. If you want a prime with 1,000 digits, for example, you could pick a 1,000-digit number at random and then check it. \u201cIf it\u2019s not prime, you just try another one, […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/\" \/>\n<meta property=\"og:site_name\" content=\"Science and Nerds\" \/>\n<meta property=\"article:published_time\" content=\"2023-07-17T21:58:18+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-07-17T21:58:19+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"2560\" \/>\n\t<meta property=\"og:image:height\" content=\"1440\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/\",\"url\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/\",\"name\":\"How to Build a Big Prime Number - Science and Nerds\",\"isPartOf\":{\"@id\":\"https:\/\/scienceandnerds.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1\",\"datePublished\":\"2023-07-17T21:58:18+00:00\",\"dateModified\":\"2023-07-17T21:58:19+00:00\",\"author\":{\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\"},\"breadcrumb\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1\",\"width\":2560,\"height\":1440},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/scienceandnerds.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"How to Build a Big Prime Number\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/scienceandnerds.com\/#website\",\"url\":\"https:\/\/scienceandnerds.com\/\",\"name\":\"Science and Nerds\",\"description\":\"My WordPress Blog\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/scienceandnerds.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\/\/scienceandnerds.com\"],\"url\":\"https:\/\/scienceandnerds.com\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"How to Build a Big Prime Number - Science and Nerds","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/","og_locale":"en_US","og_type":"article","og_title":"How to Build a Big Prime Number - Science and Nerds","og_description":"Source:https:\/\/www.quantamagazine.org\/how-to-build-a-big-prime-number-20230713\/#comments How to Build a Big Prime Number 2023-07-17 21:58:18 Over time, researchers developed the aforementioned approaches. The simplest way is just to guess. If you want a prime with 1,000 digits, for example, you could pick a 1,000-digit number at random and then check it. \u201cIf it\u2019s not prime, you just try another one, […]","og_url":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/","og_site_name":"Science and Nerds","article_published_time":"2023-07-17T21:58:18+00:00","article_modified_time":"2023-07-17T21:58:19+00:00","og_image":[{"width":2560,"height":1440,"url":"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp","type":"image\/webp"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/","url":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/","name":"How to Build a Big Prime Number - Science and Nerds","isPartOf":{"@id":"https:\/\/scienceandnerds.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage"},"image":{"@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1","datePublished":"2023-07-17T21:58:18+00:00","dateModified":"2023-07-17T21:58:19+00:00","author":{"@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e"},"breadcrumb":{"@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#primaryimage","url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1","contentUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1","width":2560,"height":1440},{"@type":"BreadcrumbList","@id":"https:\/\/scienceandnerds.com\/2023\/07\/17\/how-to-build-a-big-prime-number\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/scienceandnerds.com\/"},{"@type":"ListItem","position":2,"name":"How to Build a Big Prime Number"}]},{"@type":"WebSite","@id":"https:\/\/scienceandnerds.com\/#website","url":"https:\/\/scienceandnerds.com\/","name":"Science and Nerds","description":"My WordPress Blog","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/scienceandnerds.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/scienceandnerds.com"],"url":"https:\/\/scienceandnerds.com\/author\/admin\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/07\/how-to-build-a-big-prime-number_64b5b97aadef4.webp?fit=2560%2C1440&ssl=1","_links":{"self":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/36922","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/comments?post=36922"}],"version-history":[{"count":1,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/36922\/revisions"}],"predecessor-version":[{"id":36924,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/36922\/revisions\/36924"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media\/36923"}],"wp:attachment":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media?parent=36922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/categories?post=36922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/tags?post=36922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}