220 36877 <2428464.Y3fiYV6T29@tjmaciei-mobl1> article Path: news.gmane.org!.POSTED!not-for-mail From: Thiago Macieira Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Prime test functions Date: Sun, 11 Feb 2018 22:28:36 -0800 Lines: 78 Approved: news@gmane.org Message-ID: <2428464.Y3fiYV6T29@tjmaciei-mobl1> References: <9150311.INAnE2rANT@tjmaciei-mobl1> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1518416810 13443 195.159.176.226 (12 Feb 2018 06:26:50 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 12 Feb 2018 06:26:50 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCB4TK757YBRBGHIQTKAKGQEDLVZV3A@isocpp.org Mon Feb 12 07:26:46 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qk0-f198.google.com ([209.85.220.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1el7ZU-0002Ya-3Y for gclcip-std-proposals@m.gmane.org; Mon, 12 Feb 2018 07:26:36 +0100 Original-Received: by mail-qk0-f198.google.com with SMTP id n11sf5143006qkn.0 for ; Sun, 11 Feb 2018 22:28:41 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1518416921; cv=pass; d=google.com; s=arc-20160816; b=zPIfjiQYph32Sc9zCcEjwIOPdDHSn2dz2VBfb5B/WIv/tLCc1pjVbEFQnuAcGrDvtY 8uSOn2LAi61kwagg9PcgULMM8/Y9ywMd/5P4PCmvwPZZubBVT/88cr+8auQ7qAALkyDD TrprjCXB9ZA8LN/0q8sYugHvUN11xFY3jtEPquKwpqLc1RUBEAHCkKZlZu81yokbPjmO qp0yrSTVa1GWaHmANTedYA4IdnHXbYGtej6L7YENCVSFSmCSLJf6kiJosKBolsP6fyES hhm/JuEwlHPR4BEMZTOTdnFsZm3WZhksqTs9B0n7Uo7We3TiM3aZwIq1RZGy2s2NCSwN 8oWg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:to:from :arc-authentication-results:arc-message-signature:dkim-signature :arc-authentication-results; bh=mINGwT4zvYZptEflHw1AfV9usTImFZwsj0kHLE1DU0M=; b=wFnEGoo0ncXpc2u+oTIOiSFDB8kyVdyczV1L5STavS3MmFvJl6Y/whgtx8yiEswAg3 SQnNBmRJkSRv8ofLrDgAim3g4rvAHwg5S3hKu1rAXWPskRRPudsvUU6MpRgs6vIOU77a M00s65Jpu9dXiMo+rj/HF3xbtyVgeEdJeJR8+OwOqgHibxeNf2JmHLOfTZP4BUsnNyLA TB48xUJPKcsp8wEx/vmVUCIA78ExJXqepSKcYMdVHmVLjsuEzf+cH/0iSMr5+PZHNlAd djCaDzsr03vfxhHFzDWqBL80rcXDEi54hCOzu71OGHfBzVKmQ4UNlyR+TMzO5ziLmnbs 9v3Q== ARC-Authentication-Results: i=2; mx.google.com; spf=pass (google.com: domain of thiago@macieira.org designates 2001:19f0:5:2221::1:3 as permitted sender) smtp.mailfrom=thiago@macieira.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=mINGwT4zvYZptEflHw1AfV9usTImFZwsj0kHLE1DU0M=; b=Fv/WeLFEfCrIFVH6HNRGgDOftny1MHp695ojSedbKI8ZaCeDKLkUA0NyyywHZUfVrH aaU0lMCHpxkiaDS5EVyQ465kFcH3QzfeuSwbdvUQi0LlP2Ri2XbkqyvgkwLoZeuLjjoE Y3JpU0adqX0rIKrSkf3VfKaNmV3POUTcOs47lYo2d6PBahSBEo4m0eCkz4gxUo5qeLDw hz4rWXHNDqpAldo5YpOdFuwaECdFVkve/yTRXS8Xfk9tfWYA9LL144ELx4vSS6MWHnD+ fUMFEpOQpTlHQxHtZRpo9pqY+kZS3ipV6v/ohDU8WVYJRm7NEwRS2tYeWnQ52qv91MvA WfpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=mINGwT4zvYZptEflHw1AfV9usTImFZwsj0kHLE1DU0M=; b=SxnPTUiLwXOfTK3FAwV1BKjfBnqdaGUyTEcbOX8NvZrBNOiRKR56WFK8oz1qyue8Ju tfe4wjZoSDrPjSH3hK17pg1IhOKoV4hvN04vWwh/XogNc+58nlLRlNz4af3JJE1hjQ9L yiSLjR7e8XecWEnHYe7qyrST4OVccn9cTcQ6bzHie/IeuglXnB616EWoElAhOn28mo+B F8HHG6LBIf5QTsMdlsEN1N6eY0NnCO05sMLeJ46u77JfoukI7+tDswEtUmCfuszdJiab /wklp6Tgp2+AY/Ep+TCCs0mzlnCZpfKOOLGLhIcCL0aXduNkrlpUEiygx6Mb3DCR0eE/ PWM X-Gm-Message-State: APf1xPDliX6kPJ1V0Vc+xn4UhJgck1UXkfNle9VOqXaF/MM/BYuTXIW3 adhqCNzJxtuB41VG3VX+KGHR6Q== X-Google-Smtp-Source: AH8x225ILw1iIe0h1kMslUiSg2bgfWt3oFedRSoPyEr1CNLyK3LTWjiiugLyoU8L82COs3WYd+BQ1A== X-Received: by 10.237.33.225 with SMTP id m30mr6912455qtc.61.1518416921408; Sun, 11 Feb 2018 22:28:41 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.200.11.79 with SMTP id m15ls7350400qti.7.gmail; Sun, 11 Feb 2018 22:28:40 -0800 (PST) X-Received: by 10.200.33.175 with SMTP id 44mr5425362qty.305.1518416920183; Sun, 11 Feb 2018 22:28:40 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1518416920; cv=none; d=google.com; s=arc-20160816; b=tJL+NMLnJ3Ox/R+41noQ7ALK/b47tNWUlIS0lrOV6FKl5odQ4R0F/r7AeTQLw6V2mB qjQ1rB+0u69QVpVs33Dc/bTdTimJdJd33xhY94HenHvIAbEB9U7KrsCu2m0sh21EEHmX FPFwgKhLAQVuB9TkVI8vafULS4p6F4D4DRI0anfmSgSLH9f5OIQNpc+k3Z7SDusU5k38 Gn+g2usG5uECgR3qaVnvfBs3JwU8VM4UTYi0BaPD6ZzIzLD34MvedtrCD6QxTBIkv+1D RyPnzIQm9+UmVngs9AE1xuOuTAhk1DAfW2YOpR0ZBTs59b9XHV1SstOUjK6K/7DME+Bx zFMQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:arc-authentication-results; bh=4V1pWYkKcD+dp6jD1TwTyYncI3WB893GWnyAGvYntDU=; b=VlmWhRo4U2QZi4QPeoCuicR96yGlKzgZ/zASr4lVtJT9tl2HZFig6WGy0jzny1LqUn bmq/9p/gqU1LenmSQ78Fj3zQQ4ZhD/EN+/DMxc6I/8blZ0tj05/qCFhcIQ9dWLCqHPCK yNDCDYXNuCrqOWTri8pfUpolZ4Uj8vI86D0Vx5rmYm4zmGM0XIE439LxIJvDsraWdcQA KIDl5mKsdvc2PLDZl1pdpp2fSP0T5kkDT2PKP9RJ7WiEBnIIS0+5xbQJ05H/lQh8j7nV NKDwnagJiAneEZOeVec/I0X1Gy0JwYEzXF1cN9Rv3X9snwT0AzdwUs+94CCWy2FWbb/e j7JA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of thiago@macieira.org designates 2001:19f0:5:2221::1:3 as permitted sender) smtp.mailfrom=thiago@macieira.org Original-Received: from smtp.macieira.info (smtp.macieira.info. [2001:19f0:5:2221::1:3]) by mx.google.com with ESMTPS id r7si2641066qtd.167.2018.02.11.22.28.39 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 11 Feb 2018 22:28:39 -0800 (PST) Received-SPF: pass (google.com: domain of thiago@macieira.org designates 2001:19f0:5:2221::1:3 as permitted sender) client-ip=2001:19f0:5:2221::1:3; Original-Received: from tjmaciei-mobl1.localnet (unknown [IPv6:2601:1c0:4501:5f9f:b18a:d68b:6328:33c8]) by smtp.macieira.info (Postfix) with ESMTPSA id 6F86481EA for ; Sun, 11 Feb 2018 22:28:38 -0800 (PST) In-Reply-To: X-Original-Sender: thiago@macieira.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of thiago@macieira.org designates 2001:19f0:5:2221::1:3 as permitted sender) smtp.mailfrom=thiago@macieira.org Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:36877 Archived-At: On domingo, 11 de fevereiro de 2018 14:04:39 PST Alexander Zaitsev wrote: > =D0=B2=D0=BE=D1=81=D0=BA=D1=80=D0=B5=D1=81=D0=B5=D0=BD=D1=8C=D0=B5, 11 = =D1=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=B3., 23:55:48 UTC+3 =D0= =BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Thiag= o > Macieira =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB: > > Please add answers to these questions: Please note I didn't ask you to answer in the mailing list. I asked you to = add=20 this to the paper, as supporting evidence of why the committee should consi= der=20 it. > 1. Honestly, i don't know how I can measure frequency of using these > functions. Depends on your domain. E.g. prime numbers are widely-used = in > cryptography. Also using prime numbers are required for some hash > techniques. That's the information you should talk about: what domains need this functi= on?=20 Explain how those domains need to deploy the same function over and over=20 again. This should also indicate which implementation you should recommend. Note I also said *besides* cryptography. > 2. About numbers wider than 64 bits - we have proposals about wide_int > (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0539r2.html)= . > Also i am working on Unbounded integer. We can add interoperability wi= th > these types later. I'm not asking for implementations wider than 64-bit. I was saying that=20 cryptography will need larger than 64-bit (much larger) and therefore won't= be=20 using the standard library implementation anyway. But this is a good point: of those other uses that you must surely know of,= is=20 dealing with numbers larger than 64-bit a common occurrence? > 4. Question about complexities is open. Because there are a > lot of algorithms for prime check with different complexities. For is_pri= me > i added O(sqrt(N)), but there are faster algorithms. If we are talking > about is_probable_prime, for now i am not sure which complexity should be > chosen here. Do you have any ideas? > 5. Should i suggest complete implementation or just names of possible > algorithms? See Arthur's reply about is_probable_prime. For is_prime, I would list a simple implementation that runs in the complex= ity=20 requirement, if it is of reasonable size to list in the paper. If it's not = a=20 simple algorithm, then reference it by name. --=20 Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org Software Architect - Intel Open Source Technology Center --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/2428464.Y3fiYV6T29%40tjmaciei-mobl1. .