施用中语言实现整数的因子分解算法

/*使用中语言实现整数的因子分解算法.
此程序翻译自gmp库的演示文件factorize.c.

中语言计算技术研究与发展联盟 舒生羽 2012.12.13
*/
/* Factoring with Pollard's rho method.

Copyright 1995, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2009
Free Software Foundation, Inc.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; either version 3 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.  See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program.  If not, see http://www.gnu.org/licenses/.  */
来 朴库.标准库;
来 朴库.标准进出;
来 朴库.串;



基{
    旗标_琐细: 元= 0;
    平 增量: <向>-阵= {4, 2, 4, 2, 4, 6, 2, 6};
}
使用除数求因子: (测数: <太元>-牵* 败限: 向 元)->()=
{
    若(基.旗标_琐细 > 0)
    {
        打印文套("[平凡除数 (%u)] ", 败限);
        簿冲(基.标准出口);
    }
    试因子: 向 目 元;
    测数.扫一(0) -> 试因子;
    试因子 ->>> 测数;
    环(试因子)
    {
        打印文套("2 ");
        簿冲(基.标准出口);
        --试因子;
    }
    商数, 余数: 太元;
    环(阳)
    {
        测数.截除(3, 商数, 余数);
        若(余数 != 0)
            跃;
        商数 -> 测数;
        打印文套("3 ");
        簿冲(基.标准出口);
    }
    环(阳)
    {
        测数.截除(5, 商数, 余数);
        若(余数 != 0)
            跃;
        商数 -> 测数;
        打印文套("5 ");
        簿冲(基.标准出口);
    }
    7 -> 试因子;
    失败次数: 向 元= 0;
    增量阵位: 元= 0;
    增量阵: <向>-址= 基.增量;
    环(测数 != 1 -: [向 目])
    {
        测数.截除(试因子, 商数, 余数);
        若(余数 != 0)
        {
            增量阵[增量阵位] ->+ 试因子;
            若(商数 < 试因子)
                跃;
            增量阵位 + 1 & 7 -> 增量阵位;
            失败次数++;
            若(失败次数 > 败限)
                跃;
        }
        否则
        {
            测数 <-> 商数;
            打印文套("%lu ", 试因子);
            簿冲(基.标准出口);
            0 -> 失败次数;
        }
    }
}

使用步距为参数两倍的除数求因子: (测数: <太元>-牵* 上限: 向 元* 步参: 向 目)->()=
{
    若(基.旗标_琐细 > 0)
    {
        打印文套("[平凡除数(%lu)] ", 上限);
        簿冲(基.标准出口);
    }
    余数: 太 元;
    试除数: 太 元= (2 * 步参) -: [向 目];
    1 ->+ 试除数;
    过([1 : 上限 - 1])
    {
        测数 % 试除数 -> 余数;
        环(余数 == 0 -: [向 目])
        {
            试除数 ->/ 测数;
            测数 % 试除数 -> 余数;
            //试除数.写出(基.标准出口, 10);
            试除数.写出();
            簿冲(基.标准出口);
            簿放入字(' ', 基.标准出口);
        }
        2 * 步参 ->+ 试除数;
    }
}

使用pollard_rho法求因子: (测数: <太 元>-牵* 倍余增量: 向 目* 迭代幂: 向 目)->()=
{
    若(基.旗标_琐细 > 0)
    {
        打印文套("[pollard-rho (%u)] ", 倍余增量);
        簿冲(基.标准出口);
    }
    公因子, 公因子临二: 太元;
    同余者乙: 太元(2 -: [中 目]);
    同余者甲: 太元(2 -: [中 目]);
    同余者甲_伴: 太元(2 -: [中 目]);
    差之倍: 太元(1 -: [向 目]);
    绕数: 向 田= 1;
    二之倍: 向 田= 1;
    环(测数 != 1 -: [向 目])
    {
        环(阳)
        {
            循
            {
                若(迭代幂 != 0)
                {
                    同余者甲.幂倍余(迭代幂, 测数, 同余者甲);
                    倍余增量 ->+ 同余者甲;
                }
                否则
                {
                    同余者甲 * 同余者甲 -> 公因子;
                    公因子 % 测数 -> 同余者甲;
                    倍余增量 ->+ 同余者甲;
                }
                同余者甲_伴 - 同余者甲 -> 公因子;
                差之倍 * 公因子 -> 公因子临二;
                公因子临二 % 测数 -> 差之倍;
                若(绕数 % 32 == 1)
                {
                    差之倍.共因(测数, 公因子);
                    若(公因子 != 1 -: [向 目])
                        飞 因子已寻倒;
                    同余者甲 -> 同余者乙;
                }
            }
            环(--绕数 != 0);
            差之倍.共因(测数, 公因子);
            若(公因子 != 1 -: [向 目])
                飞 因子已寻倒;
            同余者甲 -> 同余者甲_伴;
            二之倍 -> 绕数;
            2 * 二之倍 -> 二之倍;
            过([0 -: [向 田] : 绕数 - 1])
            {
                若(迭代幂 != 0)
                {
                    同余者甲.幂倍余(迭代幂, 测数, 同余者甲);
                    倍余增量 ->+ 同余者甲;
                }
                否则
                {
                    同余者甲 * 同余者甲 -> 公因子;
                    公因子 % 测数 -> 同余者甲;
                    倍余增量 ->+ 同余者甲;
                }
            }
            同余者甲 -> 同余者乙;
        }
-|因子已寻倒:
        循
        {
            若(迭代幂 != 0)
            {
                同余者乙.幂倍余(迭代幂, 测数, 同余者乙);
                倍余增量 ->+ 同余者乙;
            }
            否则
            {
                同余者乙 ->* 公因子;
                公因子 % 测数 -> 同余者乙;
                倍余增量 ->+ 同余者乙;
            }
            同余者甲_伴 - 同余者乙 -> 公因子;
            公因子.共因(测数, 公因子);
        }
        环(公因子 == 1 -: [向 目]);
        // 在公因子被写掉之前, 除以公因子
        测数.恰除(公因子, 测数);
        若(!公因子.是否概率素(25))
        {
            循
            {
                随机增量: 太支;
                太元::太数_随机(&随机增量, 1);
                随机增量 -> 倍余增量;
            }
            环(倍余增量 == 0);
            若(基.旗标_琐细 > 0)
            {
                打印文套("[复合因子--再次开始pollard-rho] ");
                簿冲(基.标准出口);
            }
            同(公因子, 倍余增量, 迭代幂);
        }
        否则
        {
            //公因子.写出(基.标准出口, 10);
            公因子.写出();
            簿冲(基.标准出口);
            簿放入字(' ', 基.标准出口);
        }
        测数 ->% 同余者甲;
        测数 ->% 同余者甲_伴;
        测数 ->% 同余者乙;
        若(测数.是否概率素(25))
        {
            //测数.写出(基.标准出口, 10);
            测数.写出();
            簿冲(基.标准出口);
            簿放入字(' ', 基.标准出口);
            跃;
        }
    }
}

因子分解: (测数: <太 元>-牵* 参数: 向 目)->()=
{
    除数上限: 向 元;
    若(测数.方向() == 0)
        归;
    // 根据测数的尺寸来设置平凡的除数限制.  
    测数.尺度(2) -> 除数上限;
    若(除数上限 > 1000)
        1000 * 1000 -> 除数上限;
    否则
        除数上限 * 除数上限 -> 除数上限;
    若(参数 != 0)
        使用步距为参数两倍的除数求因子(测数, 除数上限 / 10, 参数);
    否则
        使用除数求因子(测数, 除数上限);
    若(测数 != 1 -: [向 目])
    {
        若(基.旗标_琐细 > 0)
        {
            打印文套("[是素数吗?] ");
            簿冲(基.标准出口);
        }
        若(测数.是否概率素(25))
            //测数.写出(基.标准出口, 10);
            测数.写出();
        否则
            使用pollard_rho法求因子(测数, 1$L, 参数);
    }
}

道: (道佐长: 元* 道佐组: <口>-址-阵)->(元)=
{
    参数: 向 目;
    若(道佐长 > 1 && !串比较(道佐组[1], 1#"-v"))
    {
        1 -> 基.旗标_琐细;
        道佐组++;
        道佐长--;
    }
    若(道佐长 > 1 && !串比较(道佐组[1], 1#"-q"))
    {
        -1 -> 基.旗标_琐细;
        道佐组++;
        道佐长--;
    }
    测数: 太 元;
    若(道佐长 > 1)
    {
        0 -> 参数;
        过(阵索@[1 : 道佐长 - 1])
        {
            若(!串有长比较(道佐组[阵索], 1#"-Mp", 3))
            {
                字串变元(道佐组[阵索] + 3) -> 参数;
                1 -: [向 目] -> 测数;
                参数 -><< 测数;
                1 ->- 测数;
            }
            否则 若(!串有长比较(道佐组[阵索], 1#"-2kp", 4))
            {
                字串变元(道佐组[阵索] + 4) -> 参数;
                复;
            }
            否则
            {
                测数.获值(道佐组[阵索], 0);
            }
            若(测数 == 0 -: [向 目])
                放入串(1#"-");
            否则
            {
                因子分解(测数, 参数);
                放入串(1#"");
            }
        }
    }
    否则
    {
        环(阳)
        {
            测数.读进(基.标准入口, 0);
            若(簿尾乎(基.标准入口))
                跃;
            若(基.旗标_琐细 >= 0)
            {
                测数.写出(基.标准出口, 10);
                打印文套(" = ");
            }
            因子分解(测数, 0);
            放入串(1#"");
        }
    }
    退出(0);
}