My personal answer, to whether Hyper-Threading works under Linux.

I have been exploring this subject, through a series of experiments written in Python, and through what I learned when I was studying the subject of System Hardware, at Concordia University.

When a person uses a Windows computer, this O/S provides all the details of scheduling processes and threads. And arguably, it does well. But when a person is using Linux, the kernel makes all the required information available, but does not take care of optimizing how threads are scheduled, specifically. It becomes the responsibility of the application, or any other user-space program, to optimize how it will take up threads, using CPU affinity, or using low-level C functions that instruct the CPU to replace a single line in the L1 cache…

In the special case when a person is writing scripts in Python, because this is an interpreted language, the program which is actually running, is the Python interpreter. How well the scheduling of threads works in that case, depends on how well this Python interpreter has been coded to do so. In addition, how well certain Python modules have been coded, has a strong effect on how efficiently they schedule threads. It just so happens that I’ve been lucky, in that the Python versions I get from the Debian repositories, happen to be programmed very well. By other people.

Dirk

 

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/18/2019, 19h20 : )

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

Noticing when SageMath is using IPython, instead of Maxima.

One of the subjects of my recent postings, has been a Computer Algebra System called “SageMath”, which I was able to install on my Debian / Stretch (Debian 9) computer named ‘Plato’. One of the distinctions which I left slightly blurred about this, is the distinction between Computer Algebra, and Numerical Tools. The former refers to the ability of a computer to manipulate symbols, in the way Algebra manipulates them, but to solve equations which Humans might just find tedious or too time-consuming to solve. This can lead to answers that are theoretically exact, but which can sometimes be useless because the numerical equivalent is only available indirectly.

Numerical Tools are more numerous under Linux, and offer theoretically inexact solutions to equations, simply because the numerical answers have a limited number of decimal places after the point or comma. Yet, the numerical answers can sometimes be much more useful than Algebraic answers, for reasons that I think are self-explanatory.

SageMath offers both. In order to do Algebra, SageMath uses “Maxima” as its back-end. And under Debian Linux, installing SageMath actually installs a separate version of Maxima, which users are not supposed to use directly.

Continue reading Noticing when SageMath is using IPython, instead of Maxima.

What I’ve learned about RSA Encryption and Large Prime Numbers – How To Generate

One of the ways in which I function, is to write down thoughts in this blog, that may seem clear to me at first, but which, once written down, require further thought and refinement.

I’ve written numerous times about Public Key Cryptography, in which the task needs to be solved, to generate 1024-bit prime numbers – or maybe even, larger prime numbers – And I had not paid much attention to the question, of how exactly to do that efficiently. Well only yesterday, I read a posting of another blogger, that inspired me. This blogger explained in common-sense language, that a probabilistic method exists to verify whether a large number is prime, that method being called “The Miller-Rabin Test”. And the blogger in question was named Antoine Prudhomme.

This blogger left out an important part in his exercise, in which he suggested some working Python code, but that would be needed if actual production grade-code was to generate large prime numbers for practical cryptography. He left out the eventual need, to perform more than just one type of test, because this blogger’s main goal was to explain the one method of testing, that was his posting subject.

I decided to modify his code, and to add a simple Fermat Test, simply because (in general,) to have two different probabilistic tests, reduces the chances of false success-stories, even further than Miller-Rabin would reduce those chances by itself. But Mr. Prudhomme already mentioned that the Fermat Test exists, which is much simpler than the Miller-Rabin Test. And, I added the step of just using a Seive, with the known prime numbers up to 65535, which is known not to be prime itself. The combined effect of added tests, which my code performs prior to applying Miller-Rabin, will also speed the execution of code, because I am applying the fastest tests first, to reduce the total number of times that the slower test needs to be applied, in case the candidate-number could in fact be prime, as not having been eliminated by the earlier, simpler tests. Further, I tested my code thoroughly last night, to make sure I’ve uploaded code that works.

Here is my initial, academic code:

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

 

(Corrected 10/03/2018, 23h20 … )

(Updated 10/08/2018, 9h25 … )

Continue reading What I’ve learned about RSA Encryption and Large Prime Numbers – How To Generate