Re-entrant C++/MFC programming

• Download demo project - 102 Kb
• Download source - 18.2 Kb

Introduction

This program demonstrates a re-entrant algorithm implemented in C++/MFC. The algorithm is deterministic, and so is effectively useless for large numbers (RSA Challenge), but does demonstrate re-entrant techniques.

Background

The RSA Challenge (see their web page) involves factoring a large number, which is the product of two large prime numbers. There is a cash award, so I started looking at the problem. I came up with this algorithm, which effectively gets the possible values for the solution numbers (or one of them, which is enough) based on the input number (the challenge). The program/algorithm works fine, and is very fast for numbers up to 20 digits (base ten) but is not suitable for fast factoring of larger numbers. The time of computation goes up by a factor of ten for each additional digit, so the RSA Challenge is safe from this algorithm.

The Algorithm

The algorithm is deterministic, which means it searches every possible combination of numbers for the factors (well, not all - there are constraints). For a number A as the product of two primes greater than 11, B and C, the expansion in terms of the individual digits of B and C is like:

order n
n = 5       n = 4       n = 3          n = 2          n = 1          n = 0

a(5)        a(4)        a(3)           a(2)           a(1)           a(0)  

nCarry(4)   nCarry(3)   nCarry(2)      nCarry(1)      nCarry (0)     no nCarry

b(5)*c(0)   b(4)*c(0)   b(3)*c(0)      b(2)*c(0)      b(1)*c(0)      b(0)*c(0)  
b(4)*c(1)   b(3)*c(1)   b(2)*c(1)      b(1)*c(1)      b(0)*c(1)      ---------
b(3)*c(2)   b(2)*c(2)   b(1)*c(2)      b(0)*c(2)      ----------     sum (0)
b(2)*c(3)   b(1)*c(3)   b(0)*c(3)      ---------      sum (1)
b(1)*c(4)   b(0)*c(4)   ---------      sum (2)                       sum(0) mod 10 
b(0)*c(5)   ---------   sum (3)                                             = a(0)
---------   sum (4)                                      sum(1) mod 10 
sum (5)                                                            = a(1)
                                             sum(2) mod 10 
                                                    = a(2)
                        sum(3) mod 10 
                                = a(3)
            sum(4)
            mod 10 
            = a(4)  
sum(5) 
mod 10 
= a(5)

Starting at the lowest digit, only the lowest digit of the factors contribute. So, if the lowest digit of A is 1, then the only possibilities for the lowest digits of B and C are: 9,9; 7,3; 3,7; and 1,1 with carries of 8, 2, 2 and 0, respectively. Only 4 possible combinations. This is good. However, for the higher order digits of A, the number of combinations is 10 each. Better than trying all 100 combinations (0-9 for B and C, separately), but still a lot of possibilities when the order of A is large...

For the first order digit of A, a(1), the previous possible values of b(0) and c(0) contribute, and the combinations of b(1) and c(1) are determined, for one set of the four from order zero. For a(2), the combinations of the values of b(2) and c(2) are determined, for one set of the values of the first order, for one of the values of the zero order, and so on...

When there are no possible combinations, the algorithm is to back up to the last order, move to the next in the list of combinations for that order, and proceed again.

Assume the order of C is less than the order of B. When the order of calculation is higher than the order of C, then only five possible values are found for b(n), the c(n) being zero.

When the order of the calculation is above the order of both B and C, then there are no possible values to manipulate. The calculation can only go above the order of B if the lower numbers have a product very close to A. When the order of calculation reaches the order of A, the carry is tested (it must be zero) as well as the digit.

There is one detail of prime numbers above 10 that makes the algorithm 60% faster: all primes greater than 11 have a zero-order digit of 1, 3, 7 or 9. Only four possible values instead of ten. For a number A of order 100, B of order 75, and C of order 25, there are still 4*10E24 possible combinations up to the order of C. This is why I say that the RSA Challenge numbers are safe from this algorithm. The number of returns on the stack for this algorithm is also the number of digits of A (order plus 1).

The problem with re-entrant programs are the inherent difficulty of interrupting the execution. This program uses a class-scope variable to test for interruption, but the execution is so intensive that the menu item Stop Execution does not respond. A solution to this would be to have a worker thread doing the calculation and the main thread interacting with the GUI (not done here, that would be more appropriate for a sample for Threads).

The Succinct Summary of Re-Entrant Programming

1. The basic idea of a re-entrant routine is a routine that calls itself.
2. The best use is when an algorithm has the same set of actions for any position in a list of actions, and the result of the actions causes a BACK_UP in the control flow. The search traversal of trees (B-Trees, etc.) is a perfect example.
3. The back-up means that the algorithm returns to the last action taken, and is re-evaluated there. So, a re-entrant routine must always return a value to be tested.
4. A re-entrant routine calls itself, and so is stack-oriented.
5. Each call puts a set of values on the stack, and can quickly cause a stack overflow.
6. The cause of problems with re-entrant routines is typically a lack in the limiting test for returning: in other words: when does it stop?
7. The case demonstrated here is simple in that the limit is the size of the input number and the test is performed at the start of the re-entrant routine. (Note: LISP is totally re-entrant!)

Using the code

A brief description of re-entrant programming is nearly impossible, and this code is probably useless except as a guide and example. Comments in the code are sufficient for understanding the principle. The algorithm is also described in comments.

Points of Interest

While writing the program, I decided to allow for alternate-base number systems such as base 2, base 16, or base 12 (for old IBM people...). I use MAPLE to convert to an alternate base (like base 47, or base 60), and input the numbers through a file. However, the sample code does not implement this. If you want to, it can be set by changing the define COMPBASE in StdAfx.h. There are a couple of other interesting things in the sample code, like disabling the ENTER key (it closes down a Dialog), and using *.SetFocus() for the input edit box. I did feel free to mix bool and BOOL types, mix straight C-code and C++/MFC, and name the variables for what they do.

History

• 2002 - started the program, got it to work.
• 2003 - tried various mutations of the program, including multithreading, different bases, and constraints on the numbers to get a fast answer to RSA Challenge. Figured out that it was too slow.
• 2004 - Submit to Code Project as an example of re-entrant programming in C/C++/MFC.

References

1. A web site: The RSA Challenge.
2. A book: “Factorization and Primality Testing”, by David Broussard, Springer-Verlag, 1989, ISBN: 0-387-97040-1.
3. LISP: check out the web, or take a course in programming languages.