近年来个人或国家都越来越重视信息安全，而数论作为一门古老而基本的学科，其所研究的许多困难问题正是信息安全中各种密码体制的奠基石。例如，判别一个正整数是否素数（简称素数判定问题）和将其分解为素因子乘积形式（简称整数分解问题）正被人们广泛关注及大量研究。　　本文首先考察了两类特殊形式数的素数判定问题。第一类是形为h·2n±1的数，当h(≠)0(mod17)时，构造了一个判定其素性的explicit广义Lucasian算法。该算法对固定的h只需两个广义Lucasian序列，并且序列的种子只依赖于h，而与扎无关。Bosma(1993)和Berrizbeitia等人(2004)分别对h(≠)0(mod3)和h(≠)0(mod5)的情形导出了explicit广义Lucasian素性判定算法。但是，当h=16m-1，m为奇数时，他们的算法失效，即不再是explicit,此时我们的算法仍是explicit，而且为确定性拟二次多项式时间的。本文在算法的构造过程中主要借助了高次剩余符号以及Eisenstein高阶互反律，即八次和十六次互反律。　　第二类是形如（2p）2n+1的数，其中p为奇素数，n为正整数。Ribemboim(1996)定义了广义费马数是形如a2n+1的数，这里a为正偶数，n为正整数。在这之前，Williams(1988)已对形为62n+1和102n+1的数分别给出了有效的素性算法。此外，Berrizbeitia等人(2003)对形为A·pn±1（其中A是一个固定的正整数，p为奇素数）的数导出了一些素性判定的方法，但这些方法不太适用于广义费马数(2p)2n+1。本文通过引入一种特别的互反律，即2p-次互反律，从而得到了关于这类数的一个有效的广义Lucasian素性算法。　　除此之外，本文还将素数判定问题推广得到素理想判别问题，并导出了一个确定性多项式时间的素理想测试算法，该算法可用于判别有限秩Dedekind整环中的素理想。我们的想法是利用剩余类环的基表示以及有限域上多项式可约性判别等算法，避免用到有限域上分解多项式，从而改进了Cohen的素理想判别算法。