Generating a Germain Prime efficiently, using Python and an 8-core CPU.

I have spent extensive time, as well as previous blog postings, exploring the subject of how to generate a Germain prime (number), in the Python (3.5) programming language, but taking advantage of parallel computing to some slight degree.

Before I go any further with this subject, I’d like to point out that generally, for production-ready applications, Python is not the best language to use. The main reason is the fact that Python is an interpreted language, even though many modern interpreted languages are compiled into bytecode before being interpreted. This makes a Python script slower by nature, than very well-written C or even C++. But what I aim to do is to use Lego-Blocks to explore this exercise, yet, to use tools which would be used professionally.

The main way I am generating prime numbers is, to start with a pseudo-random, 512-bit number (just as a default, the user can specify different bit-lengths), and then to attempt to divide this number by a list of known, definite primes, that by now only extend to 4096 (exclusively, of course), in an attempt to disprove that number prime. In about 1/8 of all cases, the number survives this test, after which I undertake a more robust, Miller-Rabin approach to try disproving it prime 192 times, probabilistically. If the number has survived these tests, my program assumes it to be prime.

Even though I’ve never been told this, the probability of a non-prime Candidate surviving even a single Miller-Rabin Test, or Witness, is very small, smaller than 1/8. This could be due to the fact that the Witness in question is raised to a high, odd exponent, in its 512-bit modulus etc., after which it would be squared some number of times. Because the first Candidate in the modulus of 4 is 3, that one actually gets squared a subsequent total of zero times. And after each exponentiation, the result could be any number in the modulus, with the possible exception of zero. It needs to become either (1) or (n-1) in the modulus of (n), for the Candidate to survive the test. (:1)

Further, there is no need for the numbers that get used as witnesses, which are pseudo-random, to be of the same, high, cryptographic quality of pseudo-random, as the candidate is, which is being tested.

But there is a sub-category of prime numbers which have recently been of greater interest to me, which is known as the Germain prime numbers, such that the Totient of that main candidate, divided by two, should also be prime. And so, if the density of prime numbers roughly equal to (n) is (1 / log(n)), and if we can assume a uniform distribution of random numbers, then the probability of finding a Germain prime is roughly (1 / (log (n))2), assuming that our code was inefficient enough actually to test all numbers. The efficiency can be boosted by making sure that the random number modulo 4 equals 3.

But one early difficulty I had with this project was, that if I needed to start with a new pseudo-random number for each candidate, on my Linux computers, I’d actually break ‘/dev/urandom’ ! Therefore, the slightly better approach which I needed to take next was, to make my initial random number the pseudo-random one, and then just to keep incrementing it by 4, until the code plodded into a Germain prime.

Even when all this is incorporated into the solution I find that with Python, I need the added advantage of parallel computing. Thus, I next learned about the GIL – The Global Interpreter Lock – and the resulting pitfalls of multi-threaded Python, which is not concurrent. Multi-threading under Python tells the O/S to allocate CPU cores as usual, but then only allows 1 core to be running at any one time! But, even under those constraints, I found that I was benefiting from the fact that my early code was able to test at least 2 candidates for primality simultaneously, those being the actual candidate, as well as its Totient divided by 2. And as soon as either candidate was disproved prime, testing on the other could be stopped quickly. This reduced the necessary number of computations dramatically, to make up for the slowness of multi-threaded Python, and I felt that I was on the right track.

The only hurdle which remained was, how to convert my code into multi-processing code, no longer merely multi-threaded, while keeping the ability for two processes, then, to send each other a shutdown-command, as soon as the present process disproved its number to be prime.

(Updated 6/01/2019, 17h35 … )

Continue reading Generating a Germain Prime efficiently, using Python and an 8-core CPU.

Refining my Python, for generating strong prime numbers…

According to an earlier posting, I had applied the (probabilistic) Miller-Rabin test, after testing whether large prime number candidates are divisible by any in a list of smaller, definite prime numbers, to generate pseudo-random numbers first, and then to continue until one was found to be prime.

That earlier effort had numerous issues, including the fact that it did not generate the kind of strong prime numbers needed for Diffie-Hellman key exchange. I have broadened my horizons slightly, and written more-up-to-date Python 3, which will generate such strong primes, as well as computing the resulting, Primitive Root, which would be used as the generator (g), if the results were ever actually used in cryptography.

I’d like to thank my friend, François Dionne, for giving me help with this project.

The resulting Python script can be downloaded from this URL:

http://dirkmittler.homeip.net/text/Generate_Prime_DMFD_ITC.py

(Updated 5/23/2019, 18h40 : )

Continue reading Refining my Python, for generating strong prime numbers…

Some Observations about Roots with Multiplicities.

One of the subjects which I had visited in my past, was to write a C++ program that approximates the roots of polynomials, but that needed to deal with ‘Doubled Roots’ in a special way, just because the search algorithm within that program, which searches for the roots, cannot deal with doubled roots. And what I found was, roots cannot only be doubled, but can have multiplicities higher than (2). After not having pondered that programming project from the past, for some time, I now come back to rethink it, and find that it can be given a lecture of sorts, all to itself.

So, this is a link to a work-sheet, in which I try to explain Roots with Multiplicities, maybe to people with limited knowledge in Calculus:

Link to Letter-Sized PDF

Link to EPUB File, for viewing on Mobile Devices

And as those two documents mention, the following is a link to the earlier blog posting, from which readers can download the C++ program, as well as to find instructions on how to compile it, on Linux computers:

Link to Earlier Blog Posting

Hence, the C++ program linked to in the earlier blog posting, needed to make use of the subject, that the two PDF Files describe.

N.B.:

(Updated 5/06/2019, 13h15 … )

Continue reading Some Observations about Roots with Multiplicities.

Example Python code, that saves text to the Linux clipboard, persistently.

There are some quirks as to how the Linux X-server clipboard works, which have been observed for some time, but which will also affect how to write a Python script / program, that saves some text to the clipboard, but with the intention that the script should exit immediately, while the copied text should remain on the clipboard.

What works against that, is the way the X11 clipboard works generally, which is, that there is no part of the actual O/S, which stores the clipboard contents. Instead, the application being copied from stores this data, and the data is not transferred until another application, or the same application, pastes it again. This has as consequence, that if the first application tries to store the data to the clipboard but then exits, and if the second application next tries to paste it, the clipboard, by first approximation, will be empty because the first application, which was holding the data, has quit.

There may exist some Linux environments in which the desktop manager takes over in a case like that, to hold a copy of the data that was Copied, but my Debian / Stretch, Plasma 5.8 computer, which I name ‘Phosphene’, fails to do so. And this is also how or why, the Plasma 5 clipboard utility, which is named ‘Klipper’, will sometimes still show that last item at the top of its clipboard history, but why that item cannot be pasted (using <Ctrl>+V), until an earlier item is selected within Klipper, and then the item of interest is selected again, so that this most-recently copied item will actually be available on the clipboard again.

In principle, ‘Klipper’ has a setting which states ‘Assure clipboard never empty’. But, long story short, that setting does not work

(Update 4/09/2019, 6h05 : )

Actually, I have learned an intricacy, of how the Plasma 5, Klipper app interacts with the X11 clipboard, and which I was not aware of before. Apparently, the actual clipboard has 3 ‘slots’: ‘Primary’, ‘Secondary’, and ‘Clipboard’. Mouse-Highlighting will cause ‘Primary’ to point to the selected text, while <Ctrl>+C Copying will cause ‘Clipboard’ to point to the selected text. After that, middle-clicking with the mouse will Paste from ‘Primary’, while <Ctrl>+V will Paste from ‘Clipboard’.

When using <Ctrl>+C, an ideally Linux-compliant application will actually leave with both clipboard targets pointing at the selection, while certain applications such as Firefox will only end up with ‘Clipboard’ pointing at the selected text.

The only real pitfall in understanding ‘Klipper’ was, the fact that while it does keep a copy of the clipboard’s contents ‘on the side’, regardless of how they were Copied, Pasting that copy directly after the application Copied from has closed, is only facilitated for middle-clicking with the mouse, not for the <Ctrl>+V -type Pasting.

However, left-clicking on one of the entries in the Klipper History will cause the ‘Clipboard’ X11 pointer to point to it, unless that just happens to be the most-recent entry.

Basically, the user community wanted an alternative to Windows, that has familiar features, and instead, the Linux developers left them a well-hidden Easter Egg. (:1)


 

I recently needed to install a Python script, which hashes a domain-name, password combination, and which has as feature the ability to save the hash-code ‘to the clipboard’, instead of just printing it out, so that the user should next be able to paste the hash-code, and in some cases do so, without the hash-code ever being displayed. This script failed to work in its original version and I needed to modify it, to get it to work the way I wanted it to work.

(Updated 4/09/2019, 15h40 … )

Continue reading Example Python code, that saves text to the Linux clipboard, persistently.