凸多边形相似判定问题

2017-12-22 07:16:35唐乐红
洛阳师范学院学报 2017年11期
关键词:利用信息

唐乐红

(福州阳光学院, 福建福州 350015)

凸多边形相似判定问题

唐乐红

(福州阳光学院, 福建福州 350015)

本文通过利用已有的秘密判定相等协议、 集合相等判定协议、 数据对应成比例判定协议, 设计出凸多边形相似判定协议, 并分析了其正确性、 安全性和复杂性.

计算几何; 集合相等; 凸多边形; 相似判定

0 引言

如果一个多边形的所有边中, 任意一条边向两方无限延长成为一条直线时, 其他各边都在这条直线的同一侧, 那么我们就称这个多边形为凸多边形(边数大于3). 生活中常见的正多边形等都是凸多边形. 判定两个凸多边形是否相似, 在数学、 物理等学科上都有很多的实际应用.

本文假定双方的计算环境是安全的, 且前提 是双方都能严格遵守协议的规程. 在满足以上条件的情况下, 利用秘密判定相等协议、 集合相等判定协议、 数据对应成比例判定协议, 本文设计出凸多边形相似判定协议.

1 基础协议

1.1 秘密判定相等协议

两个用户希望在不向对方泄露自己数据信息的情况下, 比较出各自所持有数据是否相等. 如果双方数据不相等时, 则要求任何一方都不能够知道对方的数据. 这就是秘密判定问题[1].

1.2 集合相等判定协议

两个用户各自拥有一个集合, 如何在不泄露双方各自集合信息的情况下, 判定出两个集合是否相等[2], 这就是集合相等判定问题. 协议具体如下:

输入: Alice拥有集合X={x1,…,xm},Bob拥有集合Y={y1,…,ym}.

输出: 谓词P(X,Y).

执行过程:

(3) Alice和Bob各自在本地利用商量好的散列函数, 计算出S′=hash(S)和T′=hash(T).

登录APP查看全文

猜你喜欢
利用信息
利用min{a,b}的积分表示解决一类绝对值不等式
中等数学(2022年2期)2022-06-05 07:10:50
利用一半进行移多补少
利用数的分解来思考
Roommate is necessary when far away from home
订阅信息
中华手工(2017年2期)2017-06-06 23:00:31
展会信息
中外会展(2014年4期)2014-11-27 07:46:46
信息
建筑创作(2001年3期)2001-08-22 18:48:14
健康信息
祝您健康(1987年3期)1987-12-30 09:52:32
健康信息(九则)
祝您健康(1987年2期)1987-12-30 09:52:28
健康信息(十则)
祝您健康(1986年5期)1986-12-30 09:52:22