ベスパリブ

プログラミングを主とした日記・備忘録です

ルート証明書の探し方

ルート証明書を探す作業をたまにお仕事でするのですが、私なりの探し方をまとめました。

ブラウザの場合

ブラウザの鍵マークをクリック>証明書>証明書のパス>一番上の証明書をクリック>証明書の表示

f:id:takeg:20200926130706p:plain
ブラウザの鍵マークをクリック

f:id:takeg:20200926130730p:plain
一番上のルート証明書をクリックして、「証明書の表示」をクリック

ルート証明書が見れます。

ルート証明書のダウンロード(エクスポート)も「詳細」タブの「ファイルにコピー」でできます。

f:id:takeg:20200926130923p:plain
「ファイルにコピー」でダウンロードできる

エクスポートするときのファイル形式は、

  • DER形式(DER encoded binary X.509)
  • PEM形式(Base 64 encoded X.509)
  • P7B形式(Cryptographic Message Syntax Standard)

の3種類から選べます。

ブラウザ以外の場合

ルート証明書の名前がわかっている場合

「[ルート証明書名 or 企業名] root certificate」等でググって、ダウンロードできるサイトを探します。

「GlobalSign Root CA - R2 root certificate」とかで検索して探します。

ルート証明書/中間CA証明書(SSLサーバ証明書) | サポート・お申し込みガイド | GMOグローバルサイン【公式】

ルート証明書を発行しているCA認証局は大体サイトからダウンロードできるようにしてくれているので頑張って探します。

ルート証明書の名前がわかっていない場合

OpenSSLを使います。

まず、opensslコマンドを使ってサーバとTLSなりSTARTTLSなりで通信をします。その際に-showcertsオプションを指定すると証明書チェーンが表示されるので、それを見ればルート証明書がわかります。

以下ではGmailSMTPサーバ(smtp.gmail.com)のルート証明書を探します。

> openssl s_client -connect smtp.gmail.com:587 -starttls smtp -showcerts
CONNECTED(000001C0)
depth=1 C = US, O = Google Trust Services, CN = GTS CA 1O1
verify error:num=20:unable to get local issuer certificate
verify return:1
depth=0 C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
verify return:1
---
Certificate chain
 0 s:C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
   i:C = US, O = Google Trust Services, CN = GTS CA 1O1
-----BEGIN CERTIFICATE-----
MIIEyDCCA7CgAwIBAgIQSzhrqklQvncCAAAAAHpLZDANBgkqhkiG9w0BAQsFADBC
MQswCQYDVQQGEwJVUzEeMBwGA1UEChMVR29vZ2xlIFRydXN0IFNlcnZpY2VzMRMw
EQYDVQQDEwpHVFMgQ0EgMU8xMB4XDTIwMDkwMzA2NDA0NloXDTIwMTEyNjA2NDA0
NlowaDELMAkGA1UEBhMCVVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcT
DU1vdW50YWluIFZpZXcxEzARBgNVBAoTCkdvb2dsZSBMTEMxFzAVBgNVBAMTDnNt
dHAuZ21haWwuY29tMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEDhITcefeUMYB
+nyn2h4okLuNeiWVUHA8WiGU7RQO0hcmhB5wujB7Pl8jYgIXHoOzRRmywIDIFp+V
wCQ5cFR5SaOCAl0wggJZMA4GA1UdDwEB/wQEAwIHgDATBgNVHSUEDDAKBggrBgEF
BQcDATAMBgNVHRMBAf8EAjAAMB0GA1UdDgQWBBSHRBeWPUXeRH3cDglYzWu9AJcW
cTAfBgNVHSMEGDAWgBSY0fhuEOvPm+xgnxiQG6DrfQn9KzBoBggrBgEFBQcBAQRc
MFowKwYIKwYBBQUHMAGGH2h0dHA6Ly9vY3NwLnBraS5nb29nL2d0czFvMWNvcmUw
KwYIKwYBBQUHMAKGH2h0dHA6Ly9wa2kuZ29vZy9nc3IyL0dUUzFPMS5jcnQwGQYD
VR0RBBIwEIIOc210cC5nbWFpbC5jb20wIQYDVR0gBBowGDAIBgZngQwBAgIwDAYK
KwYBBAHWeQIFAzAzBgNVHR8ELDAqMCigJqAkhiJodHRwOi8vY3JsLnBraS5nb29n
L0dUUzFPMWNvcmUuY3JsMIIBBQYKKwYBBAHWeQIEAgSB9gSB8wDxAHcAB7dcG+V9
aP/xsMYdIxXHuuZXfFeUt2ruvGE6GmnTohwAAAF0UuksiAAABAMASDBGAiEAiN7n
z854FQrffyjPiAHQWjkKnBIPaxA08/CifmKCaHUCIQCLc14iC3ac5WgDubjkXITa
SmlaVemO1Ix3eAa3g6N7kwB2AOcS8rA3fhpi+47JDGGE8ep7N8tWHREmW/Pg80vy
QVRuAAABdFLpLF8AAAQDAEcwRQIga/yh3rUb4L/1fkTTgmEMQqS/0QAmQvJfNsJr
GSwgc+oCIQD+TVQ1RU7r6ylJsPJ68N4nAZphIBMgK1fLNHfSZ3F2aTANBgkqhkiG
9w0BAQsFAAOCAQEApjaqg8SqdbyYQyck3mGS9BNytzqrbUqYqmto6KcIJvuXx83I
HDJgbSJ+u1ukUZNxs2r5D2zi5sckwu7XUJKjakz+M2gafXy6i8l3LYQQ7dawuIJa
CkkdurNlYnXqfjt1ZXLhSlmj9AF/PqKEyE0p3aBcLRbDyBkPIbPRR9QnOt6cE3rV
q8wtfzwq6qSa8e2TVe6b7pSLMMe1aVcyBY6mrXyKxcz13KwiheUg8CicptkAPBoy
w757azBTSjyPEfEpT5IomANb9AUJx4ijhyvV9MXchbNwLkhktiR9QW29VkSlXSBb
tIUdHACgD69wvelpVJlyFG/aYmWeeweg5aWFNQ==
-----END CERTIFICATE-----
 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
-----BEGIN CERTIFICATE-----
MIIESjCCAzKgAwIBAgINAeO0mqGNiqmBJWlQuDANBgkqhkiG9w0BAQsFADBMMSAw
HgYDVQQLExdHbG9iYWxTaWduIFJvb3QgQ0EgLSBSMjETMBEGA1UEChMKR2xvYmFs
U2lnbjETMBEGA1UEAxMKR2xvYmFsU2lnbjAeFw0xNzA2MTUwMDAwNDJaFw0yMTEy
MTUwMDAwNDJaMEIxCzAJBgNVBAYTAlVTMR4wHAYDVQQKExVHb29nbGUgVHJ1c3Qg
U2VydmljZXMxEzARBgNVBAMTCkdUUyBDQSAxTzEwggEiMA0GCSqGSIb3DQEBAQUA
A4IBDwAwggEKAoIBAQDQGM9F1IvN05zkQO9+tN1pIRvJzzyOTHW5DzEZhD2ePCnv
UA0Qk28FgICfKqC9EksC4T2fWBYk/jCfC3R3VZMdS/dN4ZKCEPZRrAzDsiKUDzRr
mBBJ5wudgzndIMYcLe/RGGFl5yODIKgjEv/SJH/UL+dEaltN11BmsK+eQmMF++Ac
xGNhr59qM/9il71I2dN8FGfcddwuaej4bXhp0LcQBbjxMcI7JP0aM3T4I+DsaxmK
FsbjzaTNC9uzpFlgOIg7rR25xoynUxv8vNmkq7zdPGHXkxWY7oG9j+JkRyBABk7X
rJfoucBZEqFJJSPk7XA0LKW0Y3z5oz2D0c1tJKwHAgMBAAGjggEzMIIBLzAOBgNV
HQ8BAf8EBAMCAYYwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMBIGA1Ud
EwEB/wQIMAYBAf8CAQAwHQYDVR0OBBYEFJjR+G4Q68+b7GCfGJAboOt9Cf0rMB8G
A1UdIwQYMBaAFJviB1dnHB7AagbeWbSaLd/cGYYuMDUGCCsGAQUFBwEBBCkwJzAl
BggrBgEFBQcwAYYZaHR0cDovL29jc3AucGtpLmdvb2cvZ3NyMjAyBgNVHR8EKzAp
MCegJaAjhiFodHRwOi8vY3JsLnBraS5nb29nL2dzcjIvZ3NyMi5jcmwwPwYDVR0g
BDgwNjA0BgZngQwBAgIwKjAoBggrBgEFBQcCARYcaHR0cHM6Ly9wa2kuZ29vZy9y
ZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAGoA+Nnn78y6pRjd9XlQWNa7H
TgiZ/r3RNGkmUmYHPQq6Scti9PEajvwRT2iWTHQr02fesqOqBY2ETUwgZQ+lltoN
FvhsO9tvBCOIazpswWC9aJ9xju4tWDQH8NVU6YZZ/XteDSGU9YzJqPjY8q3MDxrz
mqepBCf5o8mw/wJ4a2G6xzUr6Fb6T8McDO22PLRL6u3M4Tzs3A2M1j6bykJYi8wW
IRdAvKLWZu/axBVbzYmqmwkm5zLSDW5nIAJbELCQCZwMH56t2Dvqofxs6BBcCFIZ
USpxu6x6td0V7SvJCCosirSmIatj/9dSSVDQibet8q/7UK4v4ZUN80atnZz1yg==
-----END CERTIFICATE-----
...

このCertificate chain以下に注目します。「0」と「1」の2つの証明書情報がぶら下がっているのが見つかります(中間証明書がある場合は2とかにもなる)。

 0 s:C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
   i:C = US, O = Google Trust Services, CN = GTS CA 1O1
 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign

数字が大きいほうがルート証明書に近くなります。今回は「1」がルート証明書です。sはsubject(証明対象)でiはissuer(発行者)を意味します。ルート証明書の発行者がCA認証局なので、「GlobalSign」がCA認証局です。

ルート証明書「GlobalSign Root CA - R2」は、-----BEGIN CERTIFICATE----------END CERTIFICATE-----で囲まれたものが証明書になります。

 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
-----BEGIN CERTIFICATE-----
MIIESjCCAzKgAwIBAgINAeO0mqGNiqmBJWlQuDANBgkqhkiG9w0BAQsFADBMMSAw
HgYDVQQLExdHbG9iYWxTaWduIFJvb3QgQ0EgLSBSMjETMBEGA1UEChMKR2xvYmFs
U2lnbjETMBEGA1UEAxMKR2xvYmFsU2lnbjAeFw0xNzA2MTUwMDAwNDJaFw0yMTEy
MTUwMDAwNDJaMEIxCzAJBgNVBAYTAlVTMR4wHAYDVQQKExVHb29nbGUgVHJ1c3Qg
U2VydmljZXMxEzARBgNVBAMTCkdUUyBDQSAxTzEwggEiMA0GCSqGSIb3DQEBAQUA
A4IBDwAwggEKAoIBAQDQGM9F1IvN05zkQO9+tN1pIRvJzzyOTHW5DzEZhD2ePCnv
UA0Qk28FgICfKqC9EksC4T2fWBYk/jCfC3R3VZMdS/dN4ZKCEPZRrAzDsiKUDzRr
mBBJ5wudgzndIMYcLe/RGGFl5yODIKgjEv/SJH/UL+dEaltN11BmsK+eQmMF++Ac
xGNhr59qM/9il71I2dN8FGfcddwuaej4bXhp0LcQBbjxMcI7JP0aM3T4I+DsaxmK
FsbjzaTNC9uzpFlgOIg7rR25xoynUxv8vNmkq7zdPGHXkxWY7oG9j+JkRyBABk7X
rJfoucBZEqFJJSPk7XA0LKW0Y3z5oz2D0c1tJKwHAgMBAAGjggEzMIIBLzAOBgNV
HQ8BAf8EBAMCAYYwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMBIGA1Ud
EwEB/wQIMAYBAf8CAQAwHQYDVR0OBBYEFJjR+G4Q68+b7GCfGJAboOt9Cf0rMB8G
A1UdIwQYMBaAFJviB1dnHB7AagbeWbSaLd/cGYYuMDUGCCsGAQUFBwEBBCkwJzAl
BggrBgEFBQcwAYYZaHR0cDovL29jc3AucGtpLmdvb2cvZ3NyMjAyBgNVHR8EKzAp
MCegJaAjhiFodHRwOi8vY3JsLnBraS5nb29nL2dzcjIvZ3NyMi5jcmwwPwYDVR0g
BDgwNjA0BgZngQwBAgIwKjAoBggrBgEFBQcCARYcaHR0cHM6Ly9wa2kuZ29vZy9y
ZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAGoA+Nnn78y6pRjd9XlQWNa7H
TgiZ/r3RNGkmUmYHPQq6Scti9PEajvwRT2iWTHQr02fesqOqBY2ETUwgZQ+lltoN
FvhsO9tvBCOIazpswWC9aJ9xju4tWDQH8NVU6YZZ/XteDSGU9YzJqPjY8q3MDxrz
mqepBCf5o8mw/wJ4a2G6xzUr6Fb6T8McDO22PLRL6u3M4Tzs3A2M1j6bykJYi8wW
IRdAvKLWZu/axBVbzYmqmwkm5zLSDW5nIAJbELCQCZwMH56t2Dvqofxs6BBcCFIZ
USpxu6x6td0V7SvJCCosirSmIatj/9dSSVDQibet8q/7UK4v4ZUN80atnZz1yg==
-----END CERTIFICATE-----

ちなみにこの-----BEGIN CERTIFICATE----------END CERTIFICATE-----で囲まれた形式をPEM形式と呼びます(Base64エンコードされてる形式)。

証明書のエンコード形式の変換

おまけとして、PEM形式の証明書とDER形式の証明書の変換方法を記載します。

PEMからDERへ変換

PEM形式server.pem.crtを、DER形式server.der.crtに変換する。

> openssl x509 -inform PEM -in server.pem.crt -outform DER -out server.der.crt

DERからPEMへ変換

DER形式server.der.crtを、PEM形式server.pem.crtに変換する。

> openssl x509 -inform DER -in server.der.crt -outform PEM -out server.pem.crt

参考サイト

証明書フォーマットを変換する

OpenSSLの"Unrecognized flag modules" エラー

以下のようなエラーが出て小一時間溶かしました。

OpenSSL> rsa -noout -modules -in private.key
rsa: Unrecognized flag modules
rsa: Use -help for summary.
error in rsa
OpenSSL> req -noout -modules -in server.csr
req: Unrecognized flag modules
req: Use -help for summary.
OpenSSL> x509 -noout -modules -in server.crt
x509: Unrecognized flag modules
x509: Use -help for summary.
error in x509

もしかして:modulus

OpenSSL> rsa -noout -modulus -in private.key
Modulus=D33DDA42F3XXXX...XXXXD431587DC9
OpenSSL> req -noout -modulus -in server.csr
Modulus=D33DDA42F3XXXX...XXXXD431587DC9
OpenSSL> x509 -noout -modulus -in server.crt
Modulus=D33DDA42F3XXXX...XXXXD431587DC9

modulus(モジュラス)とは

RSAモジュラス - Wikipedia

OpenSSLの"problem creating object tsa_policy1=1.2.3.4.1" エラー

環境

現象

証明書署名要求(CSR)の確認をするコマンドを行うと、2回目以降で以下のようなエラーが発生しました。

# 初回実行はうまく動作する
OpenSSL> req -text -noout -in localhost.csr
Certificate Request:
    Data:
        Version: 1 (0x0)
        Subject: C = JP, ST = Kyoto, L = Sakyoku, O = hogehoge, CN = hogehoge.co.jp
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub:
                    04:eb:95:8d:d6:fc:53:fe:e7:3e:d7:ed:64:14:11:
                    28:de:d2:3b:2f:4a:a5:6b:fc:61:b0:8e:d3:bf:38:
                    59:15:a6:f6:d3:2a:48:7f:35:4d:12:aa:95:6e:ed:
                    dc:3e:bb:1a:e5:de:13:59:77:75:09:10:89:c9:3f:
                    ac:08:18:7a:ec
                ASN1 OID: prime256v1
                NIST CURVE: P-256
        Attributes:
            a0:00
    Signature Algorithm: ecdsa-with-SHA256
         30:45:02:20:04:da:d9:e5:67:be:c3:51:42:2e:2d:6f:c1:0c:
         78:cd:79:90:33:e8:6d:79:6d:ba:f8:c8:d2:6f:47:50:65:29:
         02:21:00:bf:fa:4d:7b:51:83:67:ba:99:c1:ae:eb:6a:c1:9a:
         78:3a:6f:a8:6f:27:db:25:91:90:93:41:7b:f6:a2:85:8d
# 2回目以降は、全く同じコマンドを打ってもエラーが発生する。
OpenSSL> req -text -noout -in localhost.csr
problem creating object tsa_policy1=1.2.3.4.1
27948:error:08064066:object identifier routines:OBJ_create:oid exists:crypto\objects\obj_dat.c:698:
error in req

追記(2020/07/07)

以下のコマンドでも同現象が発生しました。

OpenSSL> req -noout -modulus -in server.csr
Modulus=D33DDA42...31587DC9
OpenSSL> req -noout -modulus -in server.csr
problem creating object tsa_policy1=1.2.3.4.1
10040:error:08064066:object identifier routines:OBJ_create:oid exists:crypto\objects\obj_dat.c:698:
error in req

やはりreqコマンド系で発生するようです。

直し方

本質的な直し方は不明です 笑。

いかがでしたか?(は?)

Ctrl-Cで一旦OpenSSLプロンプトから抜けると、とりあえず直ります。面倒くさいですが、こうする以外に私は方法を見つけれませんでした。

以下の参考URLのissueを追うと、「コマンド実行する際にライブラリコンテクストを作成し、コマンド終了時にそれをクリーンアップするのだけれど、そのクリーンアップがうまく行ってないとかなんとか」みたいに書いてありました。

よくわからないのでバグ修正待ちです。

参考

OpenSSLv1.1.0e CSR verification error, problem creating object tsa_policy1=1.2.3.4.1 · Issue #2795 · openssl/openssl

メールの改行コードはCRLFにしてね

メールの送信できね~~と思ってパケットキャプチャしたら、なんか「See http://pobox.com/~djb/docs/smtplf.html.」と怪しげなURLを見ろというパケットを発見しました。

アクセスしたら、「メールの改行コードはCRLFにしてね」という内容のページでした。

https://cr.yp.to/docs/smtplf.html

そういえばメールの本文の改行コードをLFにしてしまっていたので、CRLFに直したら、無事送信できました。

OpenSSLでメール送信するときのRCPT TOコマンドでのエラーと、記事をキャッシュで読む方法

OpenSSLを使って以下のようにメールを送信しようとしたとき、

> openssl s_client -connect smtp.mail.yahoo.co.jp:465
CONNECTED(000001C0)
...()
read R BLOCK
220 smtpgate606.mail.ssk.ynwp.yahoo.co.jp ESMTP ready
EHLO localhost
250-smtpgate606.mail.ssk.ynwp.yahoo.co.jp
250-PIPELINING
250-8BITMIME
250-SIZE 20480000
250 AUTH PLAIN LOGIN XYMYCONNECT
AUTH PLAIN
334
dGFrZxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxE=
235 ok, go ahead (#2.0.0)
MAIL FROM:<xxxxxxxxxxxxxxxxx@yahoo.co.jp>
250 ok
RCPT TO:<yyyyyyyyyy@yahoo.co.jp>
RENEGOTIATING
5428:error:1420410A:SSL routines:SSL_renegotiate:wrong ssl version:ssl\ssl_lib.c:2127:

というふうに、RCPT TOコマンドを送信するとエラーが発生して切断してしまいます。

エラー原因の詳細は以下の記事が詳しいです。

[Postfix] [OpenSSL] [解決] RENEGOTIATING SSL routines:SSL_renegotiate:wrong ssl version:ssl/ssl_lib.c - noknow

ターミナルでOpenSSL接続中、標準入力の最初の文字が"R"の場合、TLSの再ネゴシエーションとして解釈してしまうようです。

RCPT TOR の文字が原因だそうです。なんざそら。

-quietオプションをつけると解決します。

以下のように正常に動作しました。

> openssl s_client -connect smtp.mail.yahoo.co.jp:465 -quiet
depth=2 C = JP, O = "SECOM Trust Systems CO.,LTD.", OU = Security Communication RootCA2
verify error:num=20:unable to get local issuer certificate
verify return:1
depth=1 C = JP, O = "Cybertrust Japan Co., Ltd.", CN = Cybertrust Japan SureServer CA G4
verify return:1
depth=0 C = JP, ST = Tokyo, L = Chiyoda-ku, O = Yahoo Japan Corporation, CN = smtp.mail.yahoo.co.jp
verify return:1
220 smtpgate607.mail.ssk.ynwp.yahoo.co.jp ESMTP ready
EHLO localhost
250-smtpgate607.mail.ssk.ynwp.yahoo.co.jp
250-PIPELINING
250-8BITMIME
250-SIZE 20480000
250 AUTH PLAIN LOGIN XYMYCONNECT
AUTH PLAIN
334
dGFrZxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxE=
235 ok, go ahead (#2.0.0)
MAIL FROM:<xxxxxxxxxxx@yahoo.co.jp>
250 ok
RCPT TO:<yyyyyyyyyy@yahoo.co.jp>
250 ok
DATA
354 go ahead
Date: Mon, 28 Mar 2005 22:30+40 +0900
From: xxxxxxxxxxx <xxxxxxxxxxx@yahoo.co.jp>
To: yyyyyyyyyy@yahoo.co.jp
Subject: SMTP Test Mail
Message-Id: <20050328223040.1711.yyyyyyyyyy@yahoo.co.jp>
Hello.
This is test mail.
.
250 ok 1591260208 qp 95707
Quit
221 smtp6007.mail.ssk.ynwp.yahoo.co.jp

500エラーの記事を読みたい

どちらかというとこちらが本題です。

エラー内容でググると、記事がヒットするわけです。

f:id:takeg:20200604175454p:plain
検索結果

一番上の記事は、検索クエリの「routines SSL_renegotiate:wrong」という文字列が全て含まれていて、記事のタイトルにも[解決]と書いてあるので、この記事を読めば解決しそうです。

しかし、500 Internal Server Errorで見れない!

で、数十年インターネットしてて初めて知ったんですが、検索結果に出てきた記事をキャッシュで読む機能があるんですね。

f:id:takeg:20200604175753p:plain
キャッシュで読む

画像の矢印マークをクリックしたら「キャッシュ」というのが出てくるので、それをクリックすると記事が読めました。

参考

uPythonのuはマイクロのu

ガッツのGみたいな。

ひょんなことからusslのモジュールを調べていたのですが、usslのuってなんだよって思ってました。

ほかにもusocketとかusslとかujsonとかuPythonとかあります。おそらくですが、ここでのuは「マイクロ(μ)」を意味しています。

μとuが字面が似ているからというのは、なかなか気づきませんでした。

MicroPython、略してuPythonです。

ARC 054: B問題の解説(Python3)

問題:AtCoder Regular Contest 054: B - ムーアの法則

解説

微分して二分法をして解を求める方法と、三分探索をして解を求める方法があります。


問題を要約すると、x年後のコンピュータを使ってT(334)の計算が終わる時間をf(x)としたときの、 f(x) = x + \frac{P}{2^{\frac{x}{1.5}}} の最小値を求めるというもの。


 0 \leq P \leq 10^{18} という制約により、xの値を0から一個ずつ試していくという線形探索は時間がかかりすぎるので駄目っぽいのは気づきます。


 f(x)が下に凸関数ということに気づけば、以下の2つの方法のどちらかで問題を解けます。

【方法1】 f'(x)=0のとき(傾き0のとき) f(x)は最小値をとるので、 f'(x)=0となるようなxを二分探索で探せばよい。

【方法2】下に凸関数なので、 f(x)の最小値を三分探索で求める。


 f(x)が下に凸関数の条件は、「  f''(x)>=0」であること。

詳しくは上に凸,下に凸な関数と二階微分 - 高校数学の美しい物語を参照。

f:id:takeg:20200506073440j:plain

 a^{x}微分は30億年ぶりなので、間違ってるかもしれません。

ソースコード

# -*- coding:utf-8 -*-

def solve():
    """f'(x)=0となるようなxを二分法(二分探索)で求める方法"""
    import math

    P = float(input())

    def f(x):
        # f(x)
        return x + P/(2**(x/1.5))

    def fd(x):
        # f'(x)
        return 1 + P*math.log(2**(-1/1.5)) * (2**(-x/1.5))

    left, right = 0, P
    cnt = 500  # 適当
    while cnt > 0:
        cnt -= 1
        mid = (left+right)/2
        if fd(mid) == 0:
            break
        elif fd(mid) < 0:
            left = mid
            continue
        elif fd(mid) > 0:
            right = mid
            continue

    print(f(mid))


def solve2():
    """三分探索で解く方法"""
    P = float(input())

    def f(x):
        # return x + P/(2**(x/1.5))  # OverflowError: (34, 'Result too large')
        return x + P*(2**(-x/1.5))

    # f(x)は下に凸関数なので、三分探索で解く
    left, right = 0, P
    cnt = 500  # 適当
    ans = float("inf")
    while cnt > 0:
        cnt -= 1

        c1, c2 = (2*left+right)/3, (left+2*right)/3
        ret1, ret2 = f(c1), f(c2)

        if ret1 > ret2:
            left = c1
            ans = min(ans, ret2)
            continue
        else:
            right = c2
            ans = min(ans, ret1)
            continue

    print(ans)


if __name__ == "__main__":
    solve2()

注意なのですが、上の、

    def f(x):
        # return x + P/(2**(x/1.5))  # OverflowError: (34, 'Result too large')
        return x + P*(2**(-x/1.5))

の部分の書き方によって、OverflowError: (34, 'Result too large')のエラーが発生してしまいます。

3.0000
Traceback (most recent call last):
  File "c:/Users/XXXX/YYYY/022.py", line 32, in <module>
  File "c:/Users/XXXX/YYYY/022.py", line 17, in solve
    ret1, ret2 = f(c1), f(c2)
  File "c:/Users/XXXX/YYYY/022.py", line 7, in f
    return x + P/(2**(x/1.5))
OverflowError: (34, 'Result too large')

xが10000程度でも、途中計算の(2**(x/1.5))の値が大きすぎてオーバーフローして上記のようなエラーが発生します。

これを(2**(-x/1.5))と書き換えることで、途中計算でオーバーフローの発生を防げます。

計算式をプログラミングするときは、書き方に意識しましょうという問題で学びがありました。

参考