倒推因子分解法——C语言实现
倒推因子分解法是一种我自己设计实现的全新因子分解方法，它不同于以往任何的大数因子分解法，它利用递归和乘法表的原理，通过判断N值的最后一位，来反向推出它的两个因子，其本质就是试乘法的实现，对于一些较小的数其效率高于试除法，但当N值很大时其效率并不高，但是可以做为一种全新的因子分解方法学习。下面是该算法的具体实现，代码部分只可以分解PQ值相等的因子，如果有需要分解很大的数，你可能需要采用GMP库重新实现一遍即可。
/*大数分解末尾倒推法末尾倒推法是一个典型的平衡二叉树结构素数除了2、5，都是以1、3、7、9做为最后一位。1 * 1 = 1; 1 * 3 = 3; 1 * 7 = 7; 1 * 9 = 9;3 * 3 = 9; 3 * 7 = 21; 3 * 9 = 27;7 * 7 = 49; 7 * 9 = 63;9 * 9 = 81;1、9是三叉树，3、7是二叉树。二叉树对应关系是 1*3=3、7*9=63 和 1*7=7、3*9=27。三叉树对应关系是 1*1=1、3*7=21、9*9=81 和 1*9=9、3*3=9、7*7=49。所以根据N值最后一位就可以判断PQ的最后一位是什么。程序设计：赵良军2021.12.21
*/
/*字符串最后一个字节总是'\0',所以计算位数的时候要从后往前计算。RSA一个2048位的平方根是308个字节，p和q一般大小一致，也有pq距离很远的情况。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>unsigned char* g = NULL;
unsigned int depth = 5; //需要递归的字节数包括'\0',5表示寻找千位数。
unsigned char str[4096] = {'\0'};//将整形转换为字符串,支持2-36进制。
char* itoa(int value, char str[], int radix)
{char tmp_buff[33] = {0};char ch;int i = 0, j = 0;/* 超出转换进制范围，退出 */if ((radix < 2) || (radix > 36)){printf("radix err...\n");return NULL;}/* 不是10进制的负数，退出函数 */if ((value < 0) && (radix != 10)){printf("value err...\n");return NULL;}/* 10进制支持负数转换 */if ((value < 0) && (radix == 10)){value = -value;*str++ = '-';}/* 转换 */while (value){ch = value % radix;value /= radix;if (ch < 10)tmp_buff[i++] = ch + '0';else tmp_buff[i++] = ch + 'a' - 10;} /* 逆序 */for (j=i-1; j>=0; j--){*str++ = tmp_buff[j];}*str = '\0'; // 加上结束符return str;
}//查找指定的字符串
unsigned char* find_str( unsigned char* str1,char* str2,unsigned long long int n,unsigned long long int c ){unsigned char* p = str1;while( *p != '\0' ) p++;p = p - n;if( strncmp( p, str2, c ) == 0 ){return p;}else{return NULL;}
}//二叉树递归查找法void Ten( unsigned long long int aa,unsigned long long int bb,unsigned long long int carry,unsigned char* key,unsigned long long int pos,unsigned long long int n ){unsigned long long int a = aa,b = bb,c = 0;//递归退出条件if( pos == depth ){return;}if( pos == depth-1 ){printf( "key = %s\n",key );} for(int i = 0;i <= 9;i++){for(int j = 0; j <= 9;j++){c = a * b;//printf( "%d * %d = %d\n",a,b,c );//sprintf( str,"%d",c);itoa( c,str,10 );if( strcmp( str,g ) == 0 ){printf( "\n%d * %d = %s\n",a,b,str );exit(0);}unsigned char* d = find_str( str,key, pos, n );if( d == NULL ){b += carry;continue;}if( pos == depth-1 ){printf( "%d * %d = %s\n",a,b,str );}printf( "%d * %d = %s\n",a,b,str );Ten( a,b,carry*10,key-1,pos+1,n+1 );b += carry;}a += carry;b = bb;}
}//个位
void Position( char* key,int byte ){int c;g = key;depth = byte;while( *key != '\0' )key++;key = key - 1;for( int i = 1; i <= 9; i++ ){for( int j = 1; j <= 9; j++ ){c = i * j;//printf( "%d * %d = %d\n",i,j,c );sprintf( str,"%d",c );unsigned char* d = find_str( str,key, 1, 1 );if( d == NULL ){continue;}printf( "%d * %d = %s\n",i,j,str );Ten( i,j,10,key-1,2,2 );}}
}int main(){//unsigned char* p = "7793";//unsigned char* q = "9007";unsigned char* n = "70191551";//617 919//unsigned char * n = "567023";//char* n = "97049";//char* n = "57598893";//参数二求到平方根后多加一个字符Position( n,5 );/*g = n;unsigned char* p = n;printf("n = %s\n",p );while( *p != '\0' )p++;p = p - 1;if( *p == '1'){Ten( 1,1,10,p-1,2,2 ); //遍历左子树//Ten( 3,7,10,p-1,2,2 ); //遍历中子树Ten( 7,3,10,p-1,2,2 ); //遍历中子树Ten( 9,9,10,p-1,2,2 ); //遍历右子树 }else if( *p == '3'){Ten( 1,3,10,p-1,2,2 ); //遍历左子树Ten( 3,1,10,p-1,2,2 ); //遍历左子树Ten( 7,9,10,p-1,2,2 ); //遍历右子树Ten( 9,7,10,p-1,2,2 ); //遍历右子树}else if( *p == '7'){Ten( 1,7,10,p-1,2,2 ); //遍历左子树//Ten( 7,1,10,p-1,2,2 ); //遍历左子树Ten( 3,9,10,p-1,2,2 ); //遍历右子树//Ten( 9,3,10,p-1,2,2 ); //遍历右子树}else if( *p == '9'){Ten( 1,9,10,p-1,2,2 ); //遍历左子树//Ten( 9,1,10,p-1,2,2 ); //遍历左子树Ten( 3,3,10,p-1,2,2 ); //遍历中子树Ten( 7,7,10,p-1,2,2 ); //遍历右子树 }*/}