Editing Linear congruential generator (section)

=== ''m'' prime, ''c'' = 0 ===
{{main|Lehmer random number generator}}
This is the original Lehmer RNG construction. The period is ''m''−1 if the multiplier ''a'' is chosen to be a [[Primitive element (finite field)|primitive element]] of the integers modulo ''m''. The initial state must be chosen between 1 and ''m''−1.

One disadvantage of a prime modulus is that the modular reduction requires a double-width product and an explicit reduction step. Often a prime just less than a power of 2 is used (the [[Mersenne prime]]s 2<sup>31</sup>−1 and 2<sup>61</sup>−1 are popular), so that the reduction modulo ''m''&nbsp;=&nbsp;2<sup>''e''</sup>&nbsp;−&nbsp;''d'' can be computed as (''ax''&nbsp;mod&nbsp;2<sup>''e''</sup>)&nbsp;+&nbsp;''d''&nbsp;{{floor|''ax''/2<sup>''e''</sup>}}. This must be followed by a conditional subtraction of ''m'' if the result is too large, but the number of subtractions is limited to ''ad''/''m'', which can be easily limited to one if ''d'' is small.

If a double-width product is unavailable, and the multiplier is chosen carefully, '''Schrage's method'''<ref>{{cite journal
 |title=A more portable Fortran random number generator
 |first=Linus |last=Schrage
 |journal=ACM Transactions on Mathematical Software
 |volume=5 |issue=2 |pages=132–138 |date=June 1979
 |doi=10.1145/355826.355828
 |url=http://degiorgi.math.hr/aaa_sem/Rand_Gen/p132-schrage.pdf
}}</ref><ref>{{cite web
 |title=Computer Systems Performance Analysis Chapter 26: Random-Number Generation
 |first=Raj |last=Jain |date=9 July 2010
 |pages=19–20
 |url=http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19
 |access-date=2017-10-31
}}</ref> may be used. To do this, factor ''m''&nbsp;=&nbsp;''qa''+''r'', i.e. {{nobr|1=''q'' = {{floor|''m''/''a''}}}} and {{nobr|1=''r'' = ''m'' mod ''a''}}. Then compute ''ax''&nbsp;mod&nbsp;''m'' = {{nobr|''a''(''x'' mod ''q'') − ''r''{{floor|''x''/''q''}}}}. Since ''x''&nbsp;mod&nbsp;''q'' < ''q'' ≤ ''m''/''a'', the first term is strictly less than ''am''/''a''&nbsp;=&nbsp;''m''. If ''a'' is chosen so that ''r''&nbsp;≤&nbsp;''q'' (and thus ''r''/''q''&nbsp;≤&nbsp;1), then the second term is also less than ''m'': ''r''{{floor|''x''/''q''}} ≤ ''rx''/''q'' = ''x''(''r''/''q'') ≤ ''x'' < ''m''. Thus, both products can be computed with a single-width product, and the difference between them lies in the range [1−''m'',&nbsp;''m''−1], so can be reduced to [0,&nbsp;''m''−1] with a single conditional add.<ref>{{cite web
 |title=Schrage's Method
 |url=http://home.earthlink.net/~pfenerty/pi/schrages_method.html
 |first=Paul |last=Fenerty |date=11 September 2006
 |access-date=2017-10-31
 |archive-url=https://web.archive.org/web/20181230061306/http://home.earthlink.net/~pfenerty/pi/schrages_method.html
 |archive-date=2018-12-30 |url-status=dead
}}</ref>

The most expensive operation in Schrage's method is the division (with remainder) of ''x'' by ''q''; fast [[Division algorithm#Division by a constant|algorithms for division by a constant]] are not available since they also rely on double-width products.

A second disadvantage of a prime modulus is that it is awkward to convert the value 1&nbsp;≤&nbsp;''x''&nbsp;<&nbsp;''m'' to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.