binary - binary relation among prime numbers

Question

Do we have any theory stating a relation between primes in binary system. I mean, in decimal system we have a pattern stating that "a number which is divided by 1 and itself is a prime".

This was learned in my school when i was kid. But modern computation is performed on bits, in sense they are 1's and 0's. But we calculate the prime nature based on our school knowledge. It works fine when the numbers are small. But questions calculating largest prime in integers, this logic doesn't make sense.

So if there exists any theory(may be already existing) stating a relation among primes in binary represention, then we can save lot of computing power. For ex, starting with a binary representation of prime, changing or adding bits yields next prime number saves lot of computational power.

This might not make sense. But these were my thoughts from last night. Please correct me if I am wrong or it doesn't make a sense at all.

Answer 1

二进制只是将数字写为 2 的幂之和。在数学意义上，它与十进制没有显着不同。所以不，不会有任何二进制定理在十进制中没有一些平行。

在十进制中，以偶数或 5 结尾的数字不能是质数，除了 2 和 5。在二进制中，任何以偶数结尾的数字都0不能是质数，除了10（即 2）。

编辑：请参阅我几年前写的这个答案，了解如何使用二进制算术优化而不是高级数学快速生成素数的示例。这只是Erastosthenes 的一个筛子，但几千年前的数学，甚至早于十进制系统，仍然可以用于 SSE 向量化。

Answer 2

梅森素数是有趣的素数，其二进制表示不包括任何0（所以只​​有1s）

Answer 3

如果你想减少 CPU 周期来确定一个数字的素数，你应该 使用椭圆曲线方法研究分解。我不知道它是如何工作的，但它非常快。

但是，我同意所有的评论。操作二进制表示中的位来确定数字是否为素数没有任何优势。

您还可以在Emacs中运行素数分解

• Mx 计算
• 投入大量
• kf

Answer 4

素数二进制表示的一个有趣方面是有一些模式，以底部的这段代码为例。每个 True（奇数）后跟一个以相同数字结尾的数字。例如，这个素数 13，是一个奇数二进制数，后跟 3 个以 0 结尾的数字，然后是下一个素数（真）。所有二进制路径都遵循这种模式。只有素数在二进制表示中是奇数，并且跟随它们到下一个真实的数字之间的所有END直到下一个素数，它总是偶数，直到下一个奇数素数！另一个有趣的模式。所有 5 后面总是跟以 0 结尾的数字！所有 3 后面都是以 8 结尾的数字！等等！7 后跟以 2 结尾的数字。等等。我敢肯定还有更多的模式，但这很有趣，并且表明二进制数存在某种表示所有素数的基本模式。

它变得更加有趣。当偶数路径结束时，它的下一个数字总是以相同的数字结尾，以奇数结尾。例如，当以 0 结尾的数字路径结束时，下一个素数以 1 结尾。对于所有数字都是如此，它们都有一对与之相连！当以 8 结尾的数字运行结束时，下一个数字总是以 9 结尾！等等

13 1103823372545 True
14 17661173960720 False
15 282578783371520 False
16 4521260533944320 False
17 72340168543109121 True

ss = ""
for x in range(3,100):
   if isprime(x):
      ss += "1"
   else:
      ss += "0"
   print(x, int(ss,16), isprime(x))

3 1 True
4 16 False
5 257 True
6 4112 False
7 65793 True
8 1052688 False
9 16843008 False
10 269488128 False
11 4311810049 True
12 68988960784 False
13 1103823372545 True
14 17661173960720 False
15 282578783371520 False
16 4521260533944320 False
17 72340168543109121 True
18 1157442696689745936 False
19 18519083147035934977 True
20 296305330352574959632 False
21 4740885285641199354112 False
22 75854164570259189665792 False
23 1213666633124147034652673 True
24 19418666129986352554442768 False
25 310698658079781640871084288 False
26 4971178529276506253937348608 False
27 79538856468424100062997577728 False
28 1272621703494785601007961243648 False
29 20361947255916569616127379898369 True
30 325791156094665113858038078373904 False
31 5212658497514641821728609253982465 True
32 83402535960234269147657748063719440 False
33 1334440575363748306362523969019511040 False
34 21351049205819972901800383504312176640 False
35 341616787293119566428806136068994826240 False
36 5465868596689913062860898177103917219840 False
37 87453897547038609005774370833662675517441 True
38 1399262360752617744092389933338602808279056 False
39 22388197772041883905478238933417644932464896 False
40 358211164352670142487651822934682318919438336 False
41 5731378629642722279802429166954917102711013377 True
42 91702058074283556476838866671278673643376214032 False
43 1467232929188536903629421866740458778294019424513 True
44 23475726867016590458070749867847340452704310792208 False
45 375611629872265447329131997885557447243268972675328 False
46 6009786077956247157266111966168919155892303562805248 False
47 96156577247299954516257791458702706494276857004883969 True
48 1538505235956799272260124663339243303908429712078143504 False
49 24616083775308788356161994613427892862534875393250296064 False
50 393857340404940613698591913814846285800558006292004737024 False
51 6301717446479049819177470621037540572808928100672075792384 False
52 100827479143664797106839529936600649164942849610753212678144 False
53 1613239666298636753709432478985610386639085593772051402850305 True
54 25811834660778188059350919663769766186225369500352822445604880 False
55 412989354572451008949614714620316258979605912005645159129678080 False
56 6607829673159216143193835433925060143673694592090322546074849280 False
57 105725274770547458291101366942800962298779113473445160737197588480 False
58 1691604396328759332657621871084815396780465815575122571795161415680 False
59 27065670341260149322521949937357046348487453049201961148722582650881 True
60 433050725460162389160351198997712741575799248787231378379561322414096 False
61 6928811607362598226565619183963403865212787980595702054072981158625537 True
62 110860985717801571625049906943414461843404607689531232865167698538008592 False
63 1773775771484825146000798511094631389494473723032499725842683176608137472 False
64 28380412343757202336012776177514102231911579568519995613482930825730199552 False
65 454086597500115237376204418840225635710585273096319929815726893211683192832 False
66 7265385560001843798019270701443610171369364369541118877051630291386931085312 False
67 116246168960029500768308331223097762741909829912657902032826084662190897364993 True
68 1859938703360472012292933299569564203870557278602526432525217354595054357839888 False
69 29759019253767552196686932793113027261928916457640422920403477673520869725438208 False
70 476144308060280835146990924689808436190862663322246766726455642776333915607011328 False
71 7618308928964493362351854795036934979053802613155948267623290284421342649712181249 True
72 121892942863431893797629676720590959664860841810495172281972644550741482395394899984 False
73 1950287085814910300762074827529455354637773468967922756511562312811863718326318399745 True
74 31204593373038564812193197240471285674204375503486764104184997004989819493221094395920 False
75 499273493968617036995091155847540570787270008055788225666959952079837111891537510334720 False
76 7988375903497872591921458493560649132596320128892611610671359233277393790264600165355520 False
77 127814014455965961470743335896970386121541122062281785770741747732438300644233602645688320 False
78 2045024231295455383531893374351526177944657952996508572331867963719012810307737642331013120 False
79 32720387700727286136510293989624418847114527247944137157309887419504204964923802277296209921 True
80 523526203211636578184164703833990701553832435967106194516958198712067279438780836436739358736 False
81 8376419251386185250946635261343851224861318975473699112271331179393076471020493382987829739776 False
82 134022708022178964015146164181501619597781103607579185796341298870289223536327894127805275836416 False
83 2144363328354863424242338626904025913564497657721266972741460781924627576581246306044884413382657 True
84 34309813253677814787877418030464414617031962523540271563863372510794041225299940896718150614122512 False
85 548957012058845036606038688487430633872511400376644345021813960172704659604799054347490409825960192 False
86 8783312192941520585696619015798890141960182406026309520349023362763274553676784869559846557215363072 False
87 140532995087064329371145904252782242271362918496420952325584373804212392858828557912957544915445809152 False
88 2248527921393029269938334468044515876341806695942735237209349980867398285741256926607320718647132946432 False
89 35976446742288468319013351488712254021468907135083763795349599693878372571860110825717131498354127142913 True
90 575623147876615493104213623819396064343502514161340220725593595102053961149761773211474103973666034286608 False
91 9209970366025847889667417981110337029496040226581443531609497521632863378396188371383585663578656548585728 False
92 147359525856413566234678687697765392471936643625303096505751960346125814054339013942137370617258504777371648 False
93 2357752413702617059754859003164246279550986298004849544092031365538013024869424223074197929876136076437946368 False
94 37724038619241872956077744050627940472815780768077592705472501848608208397910787569187166878018177223007141888 False
95 603584617907869967297243904810047047565052492289241483287560029577731334366572601106994670048290835568114270208 False
96 9657353886525919476755902476960752761040839876627863732600960473243701349865161617711914720772653369089828323328 False
97 154517662184414711628094439631372044176653438026045819721615367571899221597842585883390635532362453905437253173249 True
98 2472282594950635386049511034101952706826455008416733115545845881150387545565481374134250168517799262486996050771984 False
99 39556521519210166176792176545631243309223280134667729848733534098406200729047701986148002696284788199791936812351744 False

Answer 5

我不知道重新开始这个话题是否有意义，但我找不到类似的方法。所以我坚持让我们开箱即用地思考。所以我开始在素数的二进制表示中寻找模式。我发现的第一件事是关于非素数的前导 0（2 除外），接下来我发现低于 100 的素数以 1 和其他一些有趣的模式开始和结束。但似乎没有一个一致的模式或所有素数的一组模式。我想如果有的话，其他计算机科学家会发现的。如果存在这些模式以找到更大的素数，这将使解密更快，并且某些身份验证更不安全，那么应用这些模式会更容易。

是否有人也对二进制素数进行研究，还是只是我想太多了？

Answer 6

我发现以下有关此主题的有趣信息。George Spelvin 在电子邮件线程中写道。

我注意到的一件事是，评论中选择质数的建议是错误地引用了 Knuth！Knuth 说（第 3 卷第 6.4 节）该数字应该与字长互质，对于二进制计算机来说，这意味着奇数。

https://lwn.net/Articles/687494/