基于身份的密码体制是现代密码学的一个研究热点，它降低了公钥密码系统中可信第三方管理公钥证书的复杂度。目前许多基于身份的密码方案都使用了椭圆曲线上的双线性对。为了使这些方案能够在工程实践中应用，对选取的椭圆曲线提出了一些限制：(1)为了保证系统的安全性，要求选取的椭圆曲线具有一个大素数阶的子群并且双线性对所映射到的有限域扩域应足够大，一般不能小于960比特；(2)从系统的计算效率考虑，要求双线性对所映射到的有限域扩域的阶应足够小。为了满足前述的两个条件，要求椭圆曲线具有适宜的嵌入次数。超奇异椭圆曲线的嵌入次数≤6，但它们的群结构比较简单，存在易受攻击的风险。为了提高系统的安全级别，通常会采用非超奇异椭圆曲线。但具有较小嵌入次数的非超奇异椭圆曲线很稀少，很难通过随机选取的方式寻找到，需要设计专门的方法来构造。目前在能有效构造具有较小嵌入次数的非超奇异椭圆曲线的方法中，分圆多项式与有理多项式的合成多项式的可约分性起着重要的作用。但可约分的合成多项式的分布很稀疏。在基于身份的密码体制中，双线性对的计算决定着整个系统的效率。通常采用Miller算法来计算双线性对。在Miller算法中许多运算在有限域的扩域中进行，为了提高计算效率，应尽量减少扩域中的乘法运算和求逆运算的次数。论文对分圆多项式与有理多项式的合成多项式的可约分性，双线性对的快速计算以及多核处理器环境下双线性对的并行计算进行了研究，取得以下主要结果。(1)给出了分圆多项式与有理多项式的合成多项式可约分的充分必要条件。根据这个充要条件，提出了一种通过构造分圆域的单代数扩域，然后利用本原元定理来构造可约分的分圆多项式与有理多项式的合成多项式的方法。该方法可以构造出所有使满足条件的有理多项式。(2)分析了双线性对计算中所利用的循环控制多项式的性质。在这个结论的基础上，给出了构造适合于双线性对计算的非超奇异椭圆曲线时，选取适宜的椭圆曲线参数的方法。还给出了利用分圆多项式与有理多项式的合成多项式的不可约分因子来生成适合于双线性对计算的非超奇异椭圆曲线，并运用Miller算法来计算Atei对时，循环次数达到理论下限的充要条件。(3)通过利用新Miller公式，改进了基于双重基链的Tate对计算方法，大大减少了二倍乘运算和三倍乘运算的计算量。改进的方法与原方法比效率提高了约23%。(4)提出一种通过构造具有一个阶为Proth型素数的子群的椭圆曲线来优化双线性对计算的方法。该方法减少了运用Miller算法计算双线性对时所需的加法运算的次数，而同时未降低子群阶的汉明重量，保证了系统的安全性。(5)将从右至左重复加倍和加方法推广到双线性对的计算中。在Miller算法中采用从右至左的计算结构，使得在同一轮循环中加法运算和二倍乘算不相关，从而可以利用处理器的两个核来并行计算Tate对。(6)提出对Miller算法中的循环控制参数进行分解，从而将Miller公式分解为三个不相关的部分，然后利用多核处理器的三个不同的核来并行计算不相关的三个分量。为了平衡各个核的计算量，提出了两种方法：一种利用椭圆曲线上的有效自同态；另一种利用预计算。