Pull back the curtain on infinity

exploring the undesigned
intelligence of the numberverse

Lists:Perfect Squares, Composites, Primes

     
home   Instantly Factor a Semiprime of Any Size!

First published August 21, 2008

 

  

 

 

What is a semiprime?
A natural number that is the product of two prime numbers. *

 

For example, if N=3405971539559

The next perfect square is:

3405973598784

The difference between N and this perfect square is:

2059225

2059225 is a perfect square

It must therefore also be the first nonadjacent* perfect square of N.

The semiprime is therefore instantly factorable!

How...?

1. The first nonadj perf. sqr is the difference: 2059225

2. The second nonadj* perf. sqr is the perfect square: 3405973598784

(The difference between these numbers must be N: 3405971539559)

3. The square roots of the nonadjacent squares are:

1435 and 1845528

4. Add and subtract these to derive the factors:

1435 + 1845528 = 1846963

1845528 - 1435 = 1844093

5. The factors are:
1846963 * 1844093

 

* Are you wondering what on earth are the 1st and 2nd nonadjacent perfect squares...?

 

 

   How I learned not to be afraid
   of big numbers!


    It's a question of magnitude....

 

 

 

 

 

 

 

 

 

 

Yes, it really is true, providing the difference between N and the next perfect square is itself a perfect square. This observation is a result of Fermat's factorization method.

 

Let's consider all integers less than 50000 and identify how many are semiprimes. First we will eliminate all evens and all primes. That leaves 24330 composite candidates. Next we must eliminate composites with more than two factors. This leaves 11740 candidate semiprimes. Finally, we will eliminate the perfect squares (though technically semiprimes). This leaves a total of 11576.

Of these semiprimes, how many conform to the type that the next perfect square minus N equals any perfect square (x2)? That is:

     (floor(√(N))+1)2 - N = x2

We know that for every semiprime there is a y such that (N+y)2 - N = x2 where y is not greater than about N/6. But the problem is that, as N becomes bigger, the N/6 ceiling becomes a relatively much bigger number - a greater number of perfect squares - than the quantity of odd numbers less than the N - and therefore a far less efficient way to find a factor than by trial division.*

However, we are considering here only the difference between N and the closest perfect square greater than N. If this difference is a perfect square, we know we can derive its factors instantly, using the procedure in the left column.

So it doesn't matter how large N is in this special case - it could be 200 digits - if it conforms to this simple formula, it can be factored instantly. There are 228 such semiprimes under 50,000, and they are shown below.

Not suprisingly, these semiprimes are the symmetrical kind - in fact, superficially, without knowing this trick, they would appear to be the 'hardest' kind for oversized Ns - where the factors are fairly close to the square root.

 N
F1
 F2
x2 
 N+x2
 √(Nx2)*
  √(Ny2)*
15 5 3 1 16 1 4
35 7 5 1 36 1 6
143 13 11 1 144 1 12
323 19 17 1 324 1 18
899 31 29 1 900 1 30
1763 43 41 1 1764 1 42
3599 61 59 1 3600 1 60
5183 73 71 1 5184 1 72
10403 103 101 1 10404 1 102
11663 109 107 1 11664 1 108
19043 139 137 1 19044 1 138
22499 151 149 1 22500 1 150
32399 181 179 1 32400 1 180
36863 193 191 1 36864 1 192
39203 199 197 1 39204 1 198
21 7 3 4 25 2 5
77 11 7 4 81 2 9
221 17 13 4 225 2 15
437 23 19 4 441 2 21
1517 41 37 4 1521 2 39
2021 47 43 4 2025 2 45
4757 71 67 4 4761 2 69
6557 83 79 4 6561 2 81
9797 101 97 4 9801 2 99
11021 107 103 4 11025 2 105
12317 113 109 4 12321 2 111
16637 131 127 4 16641 2 129
27221 167 163 4 27225 2 165
38021 197 193 4 38025 2 195
55 11 5 9 64 3 8
91 13 7 9 100 3 10
187 17 11 9 196 3 14
247 19 13 9 256 3 16
391 23 17 9 400 3 20
667 29 23 9 676 3 26
1147 37 31 9 1156 3 34
1591 43 37 9 1600 3 40
1927 47 41 9 1936 3 44
2491 53 47 9 2500 3 50
3127 59 53 9 3136 3 56
4087 67 61 9 4096 3 64
4891 73 67 9 4900 3 70
5767 79 73 9 5776 3 76
7387 89 83 9 7396 3 86
9991 103 97 9 10000 3 100
10807 107 101 9 10816 3 104
11227 109 103 9 11236 3 106
12091 113 107 9 12100 3 110
17947 137 131 9 17956 3 134
23707 157 151 9 23716 3 154
25591 163 157 9 25600 3 160
28891 173 167 9 28900 3 170
30967 179 173 9 30976 3 176
37627 197 191 9 37636 3 194
38407 199 193 9 38416 3 196
65 13 5 16 81 4 9
209 19 11 16 225 4 15
713 31 23 16 729 4 27
1073 37 29 16 1089 4 33
3233 61 53 16 3249 4 57
3953 67 59 16 3969 4 63
5609 79 71 16 5625 4 75
8633 97 89 16 8649 4 93
11009 109 101 16 11025 4 105
18209 139 131 16 18225 4 135
23393 157 149 16 23409 4 153
31313 181 173 16 31329 4 177
38009 199 191 16 38025 4 195
299 23 13 25 324 5 18
551 29 19 25 576 5 24
1271 41 31 25 1296 5 36
1739 47 37 25 1764 5 42
2279 53 43 25 2304 5 48
4331 71 61 25 4356 5 66
6059 83 73 25 6084 5 78
7031 89 79 25 7056 5 84
10379 107 97 25 10404 5 102
11639 113 103 25 11664 5 108
17399 137 127 25 17424 5 132
20711 149 139 25 20736 5 144
26219 167 157 25 26244 5 162
28199 173 163 25 28224 5 168
34571 191 181 25 34596 5 186
493 29 17 36 529 6 23
589 31 19 36 625 6 25
1189 41 29 36 1225 6 35
1333 43 31 36 1369 6 37
2173 53 41 36 2209 6 47
2773 59 47 36 2809 6 53
4189 71 59 36 4225 6 65
4453 73 61 36 4489 6 67
5293 79 67 36 5329 6 73
5893 83 71 36 5929 6 77
8989 101 89 36 9025 6 95
10573 109 97 36 10609 6 103
11413 113 101 36 11449 6 107
17653 139 127 36 17689 6 133
20413 149 137 36 20449 6 143
20989 151 139 36 21025 6 145
24613 163 151 36 24649 6 157
29893 179 167 36 29929 6 173
34189 191 179 36 34225 6 185
34933 193 181 36 34969 6 187
41989 211 199 36 42025 6 205
47053 223 211 36 47089 6 217
851 37 23 49 900 7 30
1247 43 29 49 1296 7 36
2867 61 47 49 2916 7 54
3551 67 53 49 3600 7 60
4307 73 59 49 4356 7 66
8051 97 83 49 8100 7 90
9167 103 89 49 9216 7 96
14351 127 113 49 14400 7 120
20687 151 137 49 20736 7 144
24287 163 149 49 24336 7 156
30227 181 167 49 30276 7 174
34547 193 179 49 34596 7 186
41567 211 197 49 41616 7 204
1457 47 31 64 1521 8 39
1961 53 37 64 2025 8 45
2537 59 43 64 2601 8 51
5561 83 67 64 5625 8 75
6497 89 73 64 6561 8 81
10961 113 97 64 11025 8 105
25217 167 151 64 25281 8 159
27161 173 157 64 27225 8 165
29177 179 163 64 29241 8 171
35657 197 181 64 35721 8 189
47897 227 211 64 47961 8 373
2419 59 41 81 2500 9 50
2623 61 43 81 2704 9 52
3763 71 53 81 3844 9 62
4819 79 61 81 4900 9 70
6319 89 71 81 6400 9 80
7663 97 79 81 7744 9 88
8383 101 83 81 8464 9 92
9523 107 89 81 9604 9 98
13843 127 109 81 13924 9 118
14803 131 113 81 14884 9 122
19519 149 131 81 19600 9 140
21823 157 139 81 21904 9 148
24883 167 149 81 24964 9 158
29503 181 163 81 29584 9 172
33043 191 173 81 33124 9 182
35263 197 179 81 35344 9 188
36019 199 181 81 36100 9 190
40723 211 193 81 40804 9 202
48319 229 211 81 48400 9 358
2501 61 41 100 2601 10 51
3149 67 47 100 3249 10 57
3869 73 53 100 3969 10 63
4661 79 59 100 4761 10 69
8549 103 83 100 8649 10 93
9701 109 89 100 9801 10 99
13589 127 107 100 13689 10 117
19781 151 131 100 19881 10 141
21509 157 137 100 21609 10 147
33389 193 173 100 33489 10 183
35621 199 179 100 35721 10 189
40301 211 191 100 40401 10 201
5063 83 61 121 5184 11 72
5963 89 67 121 6084 11 78
7979 101 79 121 8100 11 90
14279 131 109 121 14400 11 120
18923 149 127 121 19044 11 138
26123 173 151 121 26244 11 162
28103 179 157 121 28224 11 168
49163 233 211 121 49284 11 322
7081 97 73 144 7225 12 85
8137 103 79 144 8281 12 91
8881 107 83 144 9025 12 95
10057 113 89 144 10201 12 101
13081 127 103 144 13225 12 115
14017 131 107 144 14161 12 119
15481 137 113 144 15625 12 125
19177 151 127 144 19321 12 139
22657 163 139 144 22801 12 151
25777 173 149 144 25921 12 161
28417 181 157 144 28561 12 169
31897 191 167 144 32041 12 179
34081 197 173 144 34225 12 185
44377 223 199 144 44521 12 211
9047 109 83 169 9216 13 96
12827 127 101 169 12996 13 114
15707 139 113 169 15876 13 126
20567 157 131 169 20736 13 144
22331 163 137 169 22500 13 150
32231 193 167 169 32400 13 180
34427 199 173 169 34596 13 186
43931 223 197 169 44100 13 210
13493 131 103 196 13689 14 117
14933 137 109 196 15129 14 123
23213 167 139 196 23409 14 153
27029 179 151 196 27225 14 165
31133 191 163 196 31329 14 177
45173 227 199 196 45369 14 213
13231 131 101 225 13456 15 116
14659 137 107 225 14884 15 122
15151 139 109 225 15376 15 124
19939 157 127 225 20164 15 142
22879 167 137 225 23104 15 152
26671 179 149 225 26896 15 164
27331 181 151 225 27556 15 166
31459 193 163 225 31684 15 178
32899 197 167 225 33124 15 182
38191 211 181 225 38416 15 196
43039 223 193 225 43264 15 208
44719 227 197 225 44944 15 212
45571 229 199 225 45796 15 214
21353 163 131 256 21609 16 147
26969 181 149 256 27225 16 165
33233 199 167 256 33489 16 183
37769 211 179 256 38025 16 195
42593 223 191 256 42849 16 207
45113 229 197 256 45369 16 213
24047 173 139 289 24336 17 156
29987 191 157 289 30276 17 174
32111 197 163 289 32400 17 180
43811 227 193 289 44100 17 210
46367 233 199 289 46656 17 216
30301 193 157 324 30625 18 175
32437 199 163 324 32761 18 181
43357 227 191 324 43681 18 209
44197 229 193 324 44521 18 211
45901 233 197 324 46225 18 215
36503 211 173 361 36864 19 192
43739 229 191 361 44100 19 210
44969 233 193 400 45369 20 213
       

2008 Michael M. Ross