From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-2.8 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, FORGED_GMAIL_RCVD,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=no autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id BDEBC1F463 for ; Mon, 30 Dec 2019 19:27:31 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id DB19F1209FA; Tue, 31 Dec 2019 04:27:14 +0900 (JST) Received: from o1678948x4.outbound-mail.sendgrid.net (o1678948x4.outbound-mail.sendgrid.net [167.89.48.4]) by neon.ruby-lang.org (Postfix) with ESMTPS id B18271209ED for ; Tue, 31 Dec 2019 04:27:12 +0900 (JST) Received: by filterdrecv-p3mdw1-56c97568b5-cmkgv with SMTP id filterdrecv-p3mdw1-56c97568b5-cmkgv-18-5E0A4F90-1A 2019-12-30 19:27:12.288983789 +0000 UTC m=+1190645.883730385 Received: from herokuapp.com (unknown [3.83.47.54]) by ismtpd0084p1mdw1.sendgrid.net (SG) with ESMTP id IRcwrcFjTiOk9iIDNljmog for ; Mon, 30 Dec 2019 19:27:12.153 +0000 (UTC) Date: Mon, 30 Dec 2019 19:27:12 +0000 (UTC) From: sblackstone@gmail.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 72263 X-Redmine-Project: ruby-master X-Redmine-Issue-Id: 16468 X-Redmine-Issue-Author: steveb3210 X-Redmine-Sender: steveb3210 X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: =?us-ascii?Q?BFUuK4eMai4P3++tXj3kRvxj8NOVS6e2BaFafhHqk6qcwSRDAWXwpIIfRqBM=2F8?= =?us-ascii?Q?1eL+aZSHUGLr=2F=2FxXlZPJBtdReZqSkzpdC03PuJc?= =?us-ascii?Q?uBF+r4HrK3hM4o5sIFXs9pmuw7A4P5b0rrbZlb6?= =?us-ascii?Q?lq9wg6fI3MBn+9Ul+kvxFhoR6rYVRW8+Y9rGlSe?= =?us-ascii?Q?BSKQ2efNSczlLwknRHaHoQckJkH6vw1VeCc+9Ss?= =?us-ascii?Q?4cw9oJiOWq5GKK3yM=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 96600 Subject: [ruby-core:96600] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #16468 has been reported by steveb3210 (Stephen Blackstone). ---------------------------------------- Feature #16468: Switch to Miller-Rabin for Prime.prime? https://bugs.ruby-lang.org/issues/16468 * Author: steveb3210 (Stephen Blackstone) * Status: Open * Priority: Normal * Assignee: * Target version: ---------------------------------------- The miller-rabin algorithm is a non-deterministic primality test, however it is known that below 2**64, you can always get a deterministic answer by only checking a=[2,3,5,7,11,13,17,19,23, 29, 31, 37] Given that Prime.prime? would never respond in a reasonable amount of time for larger numbers, we can gain much more utility and performance by switching.. ``` user system total real miller_rabin: random set 0.150000 0.000000 0.150000 ( 0.152212) Prime.prime?: random set 0.270000 0.000000 0.270000 ( 0.281257) user system total real miller_rabin: 16 digits 0.010000 0.000000 0.010000 ( 0.000300) Prime.prime? 16 digits 2.200000 0.020000 2.220000 ( 2.368247) user system total real miller_rabin: 2-10000 0.030000 0.000000 0.030000 ( 0.035752) Prime.prime? 2-10000 0.020000 0.000000 0.020000 ( 0.022948) ``` ``` require 'benchmark' require 'prime' def modpow(base, power, mod) result = 1 while power > 0 result = (result * base) % mod if power & 1 == 1 base = (base * base) % mod power >>= 1; end result end def miller_rabin(n) return false if n < 2 # 0, 1 return true if n < 4 # 2, 3 return false if n % 2 == 0 # 4, 6, 8, 10 d = (n-1) s = 0 while (d % 2 == 0) s +=1 d /= 2 end # https://arxiv.org/pdf/1509.00864.pdf # # if n < 18,446,744,073,709,551,616 = 2**64, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37. # [2,3,5,7,11,13,17,19,23, 29, 31, 37].each do |a| x = modpow(a,d,n) next if x == 1 or x == (n - 1) or n == a skip = false 1.upto(s-1) do |k| x = x*x % n if x == 1 return false elsif x == (n - 1) skip = true break end end next if skip return false end return true end test_set = [] while test_set.length < 50_000 test_set << rand(1_000_000) end c = 1 Benchmark.bm(40) do |bm| bm.report("miller_rabin: random set") do test_set.each do |x| miller_rabin(x) end end bm.report("Prime.prime?: random set") do test_set.each do |x| Prime.prime?(x) end end end puts Benchmark.bm(40) do |bm| bm.report("miller_rabin: 16 digits") do miller_rabin(1000000000100011) end bm.report("Prime.prime? 16 digits") do Prime.prime?(1000000000100011) end end puts Benchmark.bm(40) do |bm| bm.report("miller_rabin: 2-10000") do (2..10000).each do |x| miller_rabin(x) end end bm.report("Prime.prime? 2-10000") do (2..10000).each do |x| Prime.prime?(x) end end end ``` -- https://bugs.ruby-lang.org/