login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A163582 Smallest pseudoprimes in ascending bases b of the form pq, where p = (b^k - 1) / (b - 1) and q = (b^k + 1) / (b + 1), both prime, with k a prime less than 100 0
341, 597871, 1010101010101010101010101010101010101, 432988561, 584645231109031, 54989488181, 48793204382746801501446610630739608190006929723969, 11694525061301 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

These numbers can be factored in O(log n) time by iterating over their multiplicative Sylow p-subgroups.

Let n be an odd integer. Its maximal multiplicative order is n - 1; the largest power of 2 dividing n - 1 is o, the maximal order of its multiplicative Sylow 2-subgroup.

Let t = (n - 1) / o.

Pick random integers x and y such that the Jacobi symbols (x/n) and (y/n) are -1; that is, x and y are quadratic nonresidues modulo n. Exponentiate both by t to produce generators of the Sylow 2-subgroup. Retain the value of y as r.

Repeatedly multiply x by y and y by r, modulo n, giving a parabolic sequence of x values. A factor may be obtained from gcd(x - 1, n), gcd(y - 1, n), gcd(x - y, n), or gcd(x + y, n). If a factor is not found quickly, choose new values of x and y.

It is often the case that one iteration is sufficient, instead of log n iterations.

LINKS

Table of n, a(n) for n=2..9.

EXAMPLE

341 = 11 * 31 is a base 2 pseudoprime; 2^340 = 1 (mod 341).

597871 = 547 * 1093 is a base 3 pseudoprime; 3^597870 = 1 (mod 597871).

1010101010101010101010101010101010101 = 909090909090909091 * 1111111111111111111 is a base 10 pseudoprime.

The smallest base 387 pseudoprime semiprime has 1204 bits:

190343478807499085058031516398268680442601127373980882552883668761244360084075072419711216782718751807174818426029099795926922432206385551671790497449073768776989824173201266255008090697631436472577273835739136689804694203609505130893771033656337490070783749133621893887506391690839509492668015407074108567267922714146861065256735761674160812989129563106060165551

which has factors

13760898475567760339045070218774452423864352937859851193617152180919304736064745532601237230112112091064203139709556823171465678472351610172571294148439637693965101978819764531439203

and

13832198467669147698314733795037532488236707098159643168713614109317850356458863385101761775345853604489406264785772143498778972143192810225278917434182848251964921160057172637819717

The large factor can be found in 8 iterations, taking six seconds on a 2GHz processor. In general, factorization requires less than a minute for numbers having fewer than 2000 bits.

CROSSREFS

Cf. A000040, A001358, A007535

Sequence in context: A317556 A006107 A015371 * A239271 A204751 A247441

Adjacent sequences:  A163579 A163580 A163581 * A163583 A163584 A163585

KEYWORD

nonn

AUTHOR

Reikku Kulon, Jul 31 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 05:26 EDT 2019. Contains 328146 sequences. (Running on oeis4.)