From: sto.mar@...
Date: 2017-05-20T09:38:28+00:00
Subject: [ruby-core:81305] [Ruby trunk Bug#13492] Integer#prime? and Prime.each might produce false positives

Issue #13492 has been updated by stomar (Marcus Stollsteimer).


@marcandre

I actually was working on the essentially same fix for the test case and about to commit; only I did want to fix the test for Math.sqrt first (which could be backported) and then switch to Integer.sqrt.

----------------------------------------
Bug #13492: Integer#prime? and Prime.each might produce false positives
https://bugs.ruby-lang.org/issues/13492#change-64981

* Author: stomar (Marcus Stollsteimer)
* Status: Closed
* Priority: Normal
* Assignee: marcandre (Marc-Andre Lafortune)
* Target version: 2.5
* ruby -v: r58436
* Backport: 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
There is a bug in Integer#prime? that might result in the method returning `true` for (very big) numbers that are not prime. Similarly, Prime.each might yield numbers that are not prime.

Integer#prime? uses `Math.sqrt(self).to_i` to determine the upper limit up to which trial divisions are carried out. However, Math.sqrt uses floating point arithmetic, which might lead to considerable differences between its result and the correct integer sqrt.

In the case where Math.sqrt returns a number that is too low, the trial division aborts too early and might miss a higher prime factor. Therefore, a non-prime number might erroneously reported to be prime.

Note that this bug probably has very low impact for practical use cases. The affected numbers are very big, probably well beyond the range where calculating Integer#prime? in a reasonable amount of time is feasible. For double precision floats, Math.sqrt().to_i should produce wrong results for integers from around `10**30` or `10**31` upwards.

Example:

``` ruby
p = 150094635296999111   # a prime number

n = p * p  # not prime
n          # => 22528399544939171409947441934790321
```

n is not a prime number and has only one prime factor, namely p. n can only be identified correctly as non-prime when a trial division with p is carried out.

However, Integer#prime? stops testing before p is reached:

```
Math.sqrt(n).to_i  # => 150094635296999104 (!)
p                  # => 150094635296999111
```

It would therefore erroneously return `true` (after a very long time of waiting for the result).

(To be precise: the method tests in batches of 30, and the highest tested number in this case would actually be 150094635296999101; the remaining numbers up to the (wrong) limit are known to be multiples of 2 or 3, and need not be tested.)

Prime.each has the same problem. It uses Prime::EratosthenesGenerator by default, which calculates the upper limit with Math.sqrt().floor (via Prime::EratosthenesSieve).

For trunk, this bug can easily be fixed by using the (new) Integer.sqrt method, see attached patch.

I'm not sure whether a patch for Ruby 2.4 and 2.3 (where Integer.sqrt is not available) is necessary.

---Files--------------------------------
0001-prime-upper-limit.patch (1.53 KB)


-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>