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

How I learned not to be afraid
of big numbers!

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